GATE CS 2006 Q48 — Graph Traversals (BFS, DFS)

In a Depth First Search (DFS) tree $T$ of an undirected graph $G$, every edge of $G$ is either a tree edge or a back edge. There are no cross edges.

Let $u$ be a leaf of $T$. Since $u$ is a leaf, its only tree edge is to its parent. Any other edge incident on $u$ in $G$ must be a back edge. Because there are no cross edges, all back edges from $u$ must connect to its ancestors in $T$.

Therefore, all neighbors of $u$ in $G$ are ancestors of $u$ in $T$. Since the ancestors of any vertex in a tree lie on a single unique path from the root to that vertex, all neighbors of $u$ must lie on the path in $T$ from the root to $u$.

Let $w$ be the neighbor of $u$ that is closest to the root of $T$. The path in $T$ from $w$ to $u$ contains all neighbors of $u$. By adding the edge $(u, w)$ to this path, we obtain a cycle in $G$ that contains $u$ and all of its neighbors. Thus, Option D is always true.