GATE 2026 DA Q.40: solution and answer

GATE 2026 · DAQ.40 · 2 marks · MCQ

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$ .

See the question in the paper

Tap to open full size

Answer and solution

ANSWER

The answer is (D): reachability in $G$ from $v$ to $u$ is exactly reachability in $G^{R}$ from $u$ to $v$ .

Official answer: DSource: Official answer key, GATE 2026 DA (IIT Guwahati)

BFS and DFS from a vertex both visit exactly the vertices reachable from it, so each statement reduces to a claim about paths. Reversing every edge turns a path $a ⇝ b$ in $G$ into a path $b ⇝ a$ in $G^{R}$ , and conversely.
(A) $u$ reached by BFS of $G^{R}$ from $v$ means there is a path $v ⇝ u$ in $G^{R}$ , which is a path $u ⇝ v$ in $G$ . DFS of $G$ from $v$ reaches $u$ only if there is a path $v ⇝ u$ in $G$ . Counterexample: $G$ has the single edge $u \to v$ . Then $G^{R}$ has the edge $v \to u$ , so BFS of $G^{R}$ from $v$ reaches $u$ , but DFS of $G$ from $v$ visits only $v$ . False.
(B) BFS in $G^{R}$ from $v$ visits the vertices that can reach $v$ in $G$ , while DFS in $G$ from $v$ visits the vertices reachable from $v$ . Take $G$ with only the edge $v \to w$ . DFS in $G$ visits ${v, w}$ , but $G^{R}$ has only the edge $w \to v$ , so BFS in $G^{R}$ from $v$ visits ${v}$ . The sets differ. False.
(C) Take $G$ with edges $v \to a$ and $v \to b$ . In $G^{R}$ the edges are $a \to v$ and $b \to v$ , so BFS from $v$ visits only $v$ , while DFS of $G$ from $v$ visits $v, a, b$ . The orders are not reverses of each other. False.
(D) If DFS of $G$ from $v$ reaches $u$ , there is a path $v ⇝ u$ in $G$ . Reversing every edge gives a path $u ⇝ v$ in $G^{R}$ . BFS of $G^{R}$ from $u$ visits every vertex reachable from $u$ , so it visits $v$ . This uses only the path correspondence, so it holds for every $G$ , with or without cycles and whether or not $G$ is strongly connected. True.

KEY IDEA

Reversing all edges reverses every path, so $v ⇝ u$ in $G$ if and only if $u ⇝ v$ in $G^{R}$ . BFS and DFS both visit exactly the reachable set, so only statements phrased through this path reversal always hold.

WATCH OUT FOR

Treating reachability from $v$ in $G^{R}$ as the same as reachability from $v$ in $G$ (options A and B), or assuming BFS and DFS orders are related by reversal (option C). Only the start and end of the path swap, not the starting vertex.

From the GATE 2026 DA paper. Every question of this paper · Download the full paper · All 28 Graph algorithms questions, with notes

GATE 2026 DA Q.40: solution and answer

Answer and solution

More Graph algorithms questions