GATE CS 2000 Q2.19 — Graph Traversals (BFS, DFS)

To determine which statement is always true, let us analyze the behavior of Depth-First Search (DFS) when we are at vertex $u$:

1. Case 1: $u$ has at least one unvisited neighbor in $G$.
   The DFS algorithm will immediately select one of these unvisited neighbors, say $v$, and visit it next.
   • In this case, $(u, v)$ is an edge in $G$.
   • $v$ becomes a child of $u$ in the DFS tree $T$, making $v$ a descendant of $u$.
2. Case 2: $u$ has no unvisited neighbors in $G$.
   Since there are no unvisited neighbors to explore directly from $u$, the DFS algorithm must backtrack from $u$.
   • Because no new vertex is visited directly from $u$, $u$ has no children in $T$. Thus, $u$ is a leaf in $T$.
   • The search backtracks to some ancestor of $u$ to find the next unvisited vertex $v$. Since $v$ is not a neighbor of $u$, the set $\{u, v\}$ is not an edge in $G$.

From Case 2, we can see that if $\{u, v\}$ is not an edge in $G$, then $u$ must have had no unvisited neighbors when it was reached, meaning we backtracked from it immediately. Thus, $u$ must be a leaf in $T$. This makes Option C always true.

Counterexample for Option D:

Consider a tree graph with edges $\{1, 2\}$, $\{2, 3\}$, and $\{1, 4\}$.

• Start DFS at $1$.
• Visit sequence: $1 \to 2 \to 3$.
• At $u = 3$, there are no unvisited neighbors. We backtrack to $2$, then to $1$.
• From $1$, we visit the next unvisited vertex $v = 4$.

Here, $\{3, 4\}$ is not an edge in $G$. However, the parent of $3$ is $2$, and the parent of $4$ is $1$. They do not share the same parent, which disproves Option D.