Practice Exercises, lecture on graphs

Exercise 1

Draw a graph that has 12 edges and at least 6 vertices. 6 of the vertices have to have degree exactly 3, all other vertices have to have degree $\leq 2$. Use as few vertices as possible.

Exercise 2

How many edges can a graph $G$ with $n$ vertices at most have, if $G$ is

(a) undirected

(b) directed

(c) undirected and contains $k$ vertices of degree 1

(d) undirected and $d$-regular (a graph is $d$-regular if every vertex has degree exactly $d$)

(e) undirected and consists of $k$ disjoint trees

Exercise 3

(a) Explain why BFS and DFS use adjacency lists and not an adjacency matrix.

(b) Why is the number of nodes with uneven degree in an undirected graph always even?

(c) Argue why an undirected graph $G = (V,E)$ with $|E| \geq |V|$ contains a cycle.

Exercise 4

A simple undirected graph is called complete if it contains an edge between every pair of distinct vertices.

(a) What does a DFS tree of a complete graph look like?

(b) What does a BFS tree of a complete graph look like?