Skip to content
GATEiit

GATE DA 2026 Q40: Reachability in a graph and its reverse

Question

Consider a directed graph G=(V,E)G = (V, E), where VV is the finite set of vertices and EE is the set of directed edges between the vertices. GG may contain cycles but there is no self-loop. Further, GG may not be strongly connected.

Let GRG^R be the graph obtained by reversing the directions of all the edges in GG without changing the set of vertices.

Assume that Breadth First Search (BFS) or Depth First Search (DFS) from any given vertex vv of a graph visits only the reachable vertices from vv in that graph.

Which of the following statements must always be true, regardless of the structure of GG?

Try it: multiple choice: exactly one correct option

Select one option
Wrong answer costs 2/3 mark in GATE.
Show answer and explanation

Answer: D (official GATE 2026 final answer key)

Concept used: A path v→uv \to u in GG is exactly a path u→vu \to v in GRG^R; BFS and DFS find the same reachable set.

First step: Reversing every edge of a path from vv to uu gives a path from uu to vv; reachability from the same start vertex is not preserved.

Full step-by-step solution

Detailed working, common mistakes and linked mock tests will be available with a free GATEiit account. Log-in is coming soon.

Share this question

WhatsAppDownload image

Source: official GATE 2026 DA question paper and final answer key, organised by IIT Guwahati. Question paper · Answer key

More Programming, Data Structures and Algorithms PYQs

PracticePractise Programming, Data Structures and Algorithms questions →Full paperAll GATE DA 2026 questions →