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

(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.

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?