Let be a directed graph and a depth first search (DFS) spanning tree in that is rooted at a vertex . Suppose is also a breadth first search (BFS) tree in , rooted at . Which of the following statements is/are TRUE for every such graph and tree ?
There are no back-edges in with respect to the tree
There are no cross-edges in with respect to the tree
There are no forward-edges in with respect to the tree
The only edges in are the edges in
ANSWER
Only statement (C) — "There are no forward-edges in with respect to the tree " — is true for every such graph and tree . Statements (A), (B) and (D) can each fail, so the correct selection is (C) alone.
Official answer: CSource: Official answer key, GATE 2024 CS1 (IISc Bengaluru)
Since T is simultaneously the DFS tree and the BFS tree of G rooted at v, the depth of any vertex in T equals its BFS level, i.e. its shortest-path distance from v in G.
BFS invariant: for every edge of (tree or non-tree), — otherwise going through u would give a shorter path to w than its assigned level.
Forward-edge test (option C): a forward edge has w as a proper descendant of u that is not its child, so . Since depth = level here, this forces , contradicting the BFS invariant. So a forward edge can never occur — statement (C) is TRUE for every valid .
Back-edge test (option A): a back edge has w as an ancestor of u, so , which never violates the invariant . So back edges are not ruled out automatically — a concrete example is needed.
Counterexample graph: vertices , edges . DFS from v (visiting c before a): tree edges (this is T); is a back edge (v is still on the stack), and is a cross edge (c is already finished).
BFS on the same graph with the same adjacency order gives , and the BFS tree edges are exactly — the same T. Both non-tree edges satisfy the BFS invariant ( and ), so T is simultaneously a valid DFS tree and a valid BFS tree of this G.
This T contains the back edge , so statement (A) is FALSE for this instance — hence not true for every .
The same T contains the cross edge , so statement (B) is also FALSE for this instance — hence not true for every .
The same example has non-tree edges (, ), so statement (D) ('the only edges in G are the edges in T') is false in general.
Hence, of the four statements, only (C) holds for every graph G and tree T satisfying the hypothesis.
KEY IDEA
When one tree is simultaneously a DFS tree and a BFS tree rooted at v, tree-depth equals BFS-level for every vertex. The BFS invariant level(w) ≤ level(u)+1 (for every edge (u,w) of G) then rules out forward edges outright, since a forward edge would force level(w) ≥ level(u)+2 — but it does not rule out back edges or cross edges, both of which are easy to realize with an explicit small graph.
WATCH OUT FOR
Assuming that once T is forced to be both the DFS and BFS tree, ALL non-tree edges are excluded (picking only C, or picking C together with A on the mistaken belief that DFS-of-a-tree-that-is-also-BFS can only ever have back edges). The safe check is to actually build a small counterexample graph and see which of A, B, D can be made false — only the forward-edge argument (C) is a genuine, unconditional proof; A, B and D each need — and have — explicit counterexamples.
From the GATE 2024 CS1 paper. Every question of this paper · Download the full paper · All 28 Graph algorithms questions, with notes
