GATE 2025 CS2 Q.29: solution and answer

Official answer: B, C, DSource: Official answer key, GATE 2025 CS2 (IIT Roorkee)

1. Statement (A): A DFS tree records the order/structure of recursive exploration (which branch was visited first), not edge counts or weights. There is no guarantee that the tree-path distance from the root to any vertex in a DFS tree equals the shortest-path (BFS) distance in $G$ — a DFS can plunge deep along one branch before backtracking to a vertex that is actually very close to the root. Hence (A) is FALSE.

2. Statement (B): For DFS on an UNDIRECTED graph, every edge of $G$ is classified as either a tree edge or a back edge — forward edges and cross edges, which can occur in directed-graph DFS, cannot occur here. This is because an undirected edge $(x,y)$ is explored from whichever endpoint DFS reaches first; by the time the other endpoint is visited, the edge is already either a tree edge or connects back to an ancestor still on the recursion stack (a back edge). So every non-tree edge is a back edge, which is one of the two cases named in statement (B) ('forward/back edge'). Hence (B) is TRUE.

3. Statement (C): This is the standard BFS-tree lemma. BFS assigns each vertex a level equal to its shortest-path distance from source $s$, discovering all level-$k$ vertices before any level-$(k+1)$ vertex. If $(u,v)$ is a non-tree edge found while scanning $u$'s neighbours, $v$ must already be at level $\text{level}(u)-1$, $\text{level}(u)$, or $\text{level}(u)+1$ — it cannot be two or more levels away, because BFS would then have discovered $v$ (or $u$) earlier through that very edge, contradicting how BFS proceeds strictly level by level. Hence the distances from $s$ to $u$ and $v$ differ by at most 1, so (C) is TRUE.

4. Statement (D): Running BFS (or equivalently DFS) from any unvisited vertex visits exactly the set of vertices reachable from it, which in an undirected graph is precisely its connected component. Repeating this process — pick an unvisited vertex, traverse, mark its whole component visited — until every vertex has been visited enumerates all connected components. This works identically whether BFS or DFS is used as the traversal. Hence (D) is TRUE.

5. Combining all four: the TRUE statements are (B), (C), (D), and (A) is FALSE.