Problem $3.$ Graph Properties $(10$ points$)$

For each question below, justify your answer with an argument $($if true$)$ or a counterexample $($if

false$).$

$($a$)$ TRUE or FALSE? If a directed graph $G$ is strongly connected, then $G$ has a simple cycle that

contains all the vertices.

Solution:

$($b$)$ TRUE or FALSE? A forest is an undirected acyclic graph, which is possibly unconnected. The

number of edges in a forest with $n$ vertices and $k$ connected components is $n-k.$

Solution:

$($c$)$ TRUE or FALSE? In a connected, undirected graph $G,$ suppose $D$ is the highest $d$ value that

results from running BFS on $G.$ It must also be true that any two vertices in $G$ are at distance

at most $2D$ from one another.

Solution: