Graph Traversals

• (A) False. In a triangle on \(s, a, b\), DFS from \(s\) may go \(s \to a \to b\), placing \(b\) at depth 2 although the edge \(sb\) puts it at distance 1.
• (B) True. If \(u\) is discovered before its neighbour \(v\), then \(v\) is discovered before \(u\) finishes, so \(v\) becomes a descendant of \(u\). Every non-tree edge therefore joins a vertex to one of its ancestors; undirected DFS has no cross edges.
• (C) True. BFS depths are shortest distances from \(s\), and an edge \((u, v)\) gives \(d(v) \le d(u) + 1\) and \(d(u) \le d(v) + 1\).
• (D) True. Restarting the search (BFS or DFS) from each unvisited vertex visits exactly one connected component per start.

Answer: B, C, D

On a tree, a vertex farthest from any start vertex is always an end of a longest path, so the second BFS measures the tree's diameter: the largest distance, in edges, between two vertices.

In the figure, a longest path starts at the lowest leaf on the far left, goes up to its neighbour and the left branching vertex, crosses to the central branching vertex, and follows the right branch through two more vertices to the rightmost leaf: 6 edges. The topmost leaf also reaches the rightmost leaf in 6 edges, and no two vertices are farther apart.

So the output is 6 whichever start vertex \(v\) is chosen.

Answer: 6

In a BFS tree the depth of every vertex equals its shortest distance from \(v\), and any edge \((u, w)\) forces \(\text{dist}(w) \le \text{dist}(u) + 1\).

• C is true. A forward edge \((u, w)\) leads to a descendant \(w\) of \(u\) that is not its child, so \(w\) is at least two levels below \(u\) in \(T\). The edge itself gives \(\text{dist}(w) \le \text{dist}(u) + 1\), a contradiction.
• A and D are false: with the edges \(v \to u\) and \(u \to v\), both searches give the tree \(v \to u\), and \(u \to v\) is a back edge.
• B is false: with the edges \(v \to a\), \(v \to b\) and \(b \to a\), a DFS that visits \(a\) first builds the tree \(v \to a\), \(v \to b\), which is also the BFS tree, and \(b \to a\) is a cross edge.

Answer: C

A DFS of an undirected graph grows one tree for each connected component: a new tree starts only when no unvisited vertex is reachable from the earlier ones. So the number of trees in the DFS forest equals the number of components.

A tree on \(t\) vertices has \(t - 1\) edges, so a forest with \(n\) vertices and \(c\) trees has \(n - c\) edges:

\[100 - c = 40 \quad\Rightarrow\quad c = 60\]

Edges of \(G\) that are not in the forest (back edges) do not change this, so \(G\) has 60 connected components.

Answer: 60