Question

Consider a directed graph \(G = (V, E)\), where \(V\) is the finite set of vertices and \(E\) is the set of directed edges between the vertices. \(G\) may contain cycles but there is no self-loop. Further, \(G\) may not be strongly connected.
Let \(G^R\) be the graph obtained by reversing the directions of all the edges in \(G\) without changing the set of vertices.
Assume that Breadth First Search (BFS) or Depth First Search (DFS) from any given vertex \(v\) of a graph visits only the reachable vertices from \(v\) in that graph.
Which of the following statements must always be true, regardless of the structure of \(G\)?

• A. If \(u\) is a reachable vertex in the BFS of \(G^R\) from \(v\), then \(u\) is also a reachable vertex in the DFS of \(G\) from \(v\).
• B. In \(G^R\), the BFS traversal from \(v\) will visit exactly the same set of vertices as the DFS from \(v\) in \(G\).
• C. The order of vertices visited in the BFS of \(G^R\) from \(v\) is the reverse of the order of vertices visited in the DFS of \(G\) from \(v\).
• D. If \(u\) is a reachable vertex in the DFS of \(G\) from \(v\), then \(v\) is also a reachable vertex in the BFS of \(G^R\) from \(u\).

Hint:

Reversing every edge on a path from v to u in G turns it into a path from u to v in G^R.

Answer 1

The Correct Option is D

Step 1: State the key lemma about reversed graphs.
For any directed graph $G$ and its edge-reversal $G^R$, and any two vertices $x, y$: $y$ is reachable from $x$ in $G$ exactly when $x$ is reachable from $y$ in $G^R$. This holds because every directed edge $p \to q$ in $G$ becomes $q \to p$ in $G^R$, so any path $x \to \cdots \to y$ in $G$ becomes the path $y \to \cdots \to x$ in $G^R$ when every edge on it is flipped, and the vertices used are identical, just traversed in the opposite direction.

Step 2: Apply the lemma with $x = v$ and $y = u$.
If $u$ is reachable from $v$ in $G$, the lemma with $x=v, y=u$ says $v$ is reachable from $u$ in $G^R$. Since the question tells us that BFS (or DFS) from any vertex visits exactly its reachable set, "$v$ reachable from $u$ in $G^R$" is the same fact as "$v$ is visited by BFS of $G^R$ starting at $u$".

Step 3: Match this to each option.
Option (D) states precisely this: if $u$ is reachable in DFS of $G$ from $v$, that is, $u$ reachable from $v$ in $G$, then $v$ is reachable in BFS of $G^R$ from $u$, that is, $v$ reachable from $u$ in $G^R$. This is the lemma itself, so it holds for every possible $G$, cyclic or not, strongly connected or not.

Step 4: Show the other three do not follow from the lemma.
Options (A), (B), and (C) all compare the reachable set from the same vertex $v$ in $G$ against the reachable set from that same $v$ in $G^R$. The lemma says nothing about these two sets being related, equal, or reversed in visiting order. They describe reachability in opposite directions of the edges and can be completely disjoint except for $v$ itself, so none of (A), (B), (C) is guaranteed by the lemma or by anything else in the problem statement.

Final Answer:
Only option (D) is guaranteed true for every directed graph $G$.