Let G be a directed graph and T a depth first search (DFS) spanning tree in G that is rooted at a vertex v. Suppose T is also a breadth first search (BFS) tree in G, rooted at v. Which of the following statements is/are TRUE for every such graph G and tree T ? A) There are no back-edges in G with respect to the tree T B) There are no cross-edges in G with respect to the tree T C) There are no forward-edges in G with respect to the tree T D) The only edges in G are the edges in T

Official answer: C) There are no forward-edges in G with respect to the tree T. Explanation: Let d(u) denote the shortest path distance from the root v to any vertex u in G. Since T is a BFS tree rooted at v, for any vertex u, the tree-path distance from v to u in T equals d(u). 1. Forward-edges: A forward-edge in a DFS tree is a non-tree directed edge (u, w) where u is an ancestor of w in T. Because w is a proper descendant of u and (u, w) is not a tree edge, the distance in T satisfies: d(w) d(u) + 2 However, if the directed edge (u, w) exists in G, the triangle inequality for shortest path distances requires: d(w) d(u) + 1 This is a contradiction. Therefore, no forward-edges can exist in G with respect to tree T. Hence, statement (C) is TRUE. 2. Back-edges and Cross-edges: Back-edges go from a descendant to an ancestor (e.g., creating a directed cycle), which satisfies d(w) d(u) + 1 because d(w) < d(u). Cross-edges can also satisfy the shortest path property. Thus, back-edges and cross-edges may exist, making (A), (B), and (D) false in general. Hence, only C is correct.

A) There are no back-edges in G with respect to the tree T

B) There are no cross-edges in G with respect to the tree T

C) There are no forward-edges in G with respect to the tree T

D) The only edges in G are the edges in T

Algorithms · Graph Traversals

Official IIT answer key · IISc Bangalore · Audited Aug 2026

Take topic test

GATE CSE 2024 Set 1 Q45 · MSQ · 2 marks

Let $G$ be a directed graph and $T$ a depth first search (DFS) spanning tree in $G$ that is rooted at a vertex $v$ . Suppose $T$ is also a breadth first search (BFS) tree in $G$ , rooted at $v$ . Which of the following statements is/are TRUE for every such graph $G$ and tree $T$ ?

Select one or more options

Key concept

Graph Traversals

Step-by-step verified solution

Examiner trap & misconception

Topic notes

How GATE tests Graph Traversals

GATE tests Graph Traversals (BFS and DFS) through deep theoretical properties rather than simple code tracing. Key emphases include edge classification (tree, back, forward, cross edges), timestamp intervals via the Parenthesis Theorem, DAG topological orderings, and structural invariants like the BFS level difference inequality and tree height versus graph diameter. Recent papers heavily favor MSQs and multi-property conceptual deductions over simple single-answer lookups.

Full Graph Traversals guide →

More on Graph Traversals

All 16 questions on Graph Traversals →

Independent practice explanation verified by the GateAI team. GATE is conducted by the IITs; question text follows the official paper.

Algorithms · Graph Traversals

Official IIT answer key · IISc Bangalore · Audited Aug 2026

Take topic test

GATE CSE 2024 Set 1 Q45 · MSQ · 2 marks

Let $G$ be a directed graph and $T$ a depth first search (DFS) spanning tree in $G$ that is rooted at a vertex $v$ . Suppose $T$ is also a breadth first search (BFS) tree in $G$ , rooted at $v$ . Which of the following statements is/are TRUE for every such graph $G$ and tree $T$ ?

Select one or more options

Key concept

Graph Traversals

Step-by-step verified solution

Examiner trap & misconception

Topic notes

How GATE tests Graph Traversals

Full Graph Traversals guide →

More on Graph Traversals

All 16 questions on Graph Traversals →

Independent practice explanation verified by the GateAI team. GATE is conducted by the IITs; question text follows the official paper.

Let $G$ be a directed graph and $T$ a depth first search (DFS) spanning tree in $G$ that is rooted at a vertex $v$ . Suppose $T$ is also a breadth first search (BFS) tree in $G$ , rooted at $v$ . Which of the following statements is/are TRUE for every such graph $G$ and tree $T$ ?

Step-by-step verified solution

Check you can still solve Graph Traversals under a clock

More from GATE CSE 2024 Set 1

More on Graph Traversals

Let $G$ be a directed graph and $T$ a depth first search (DFS) spanning tree in $G$ that is rooted at a vertex $v$ . Suppose $T$ is also a breadth first search (BFS) tree in $G$ , rooted at $v$ . Which of the following statements is/are TRUE for every such graph $G$ and tree $T$ ?

Step-by-step verified solution

Check you can still solve Graph Traversals under a clock

More from GATE CSE 2024 Set 1

More on Graph Traversals

Let GGG be a directed graph and TTT a depth first search (DFS) spanning tree in GGG that is rooted at a vertex vvv. Suppose TTT is also a breadth first search (BFS) tree in GGG, rooted at vvv. Which of the following statements is/are TRUE for every such graph GGG and tree TTT ?

Step-by-step verified solution

Check you can still solve Graph Traversals under a clock

More from GATE CSE 2024 Set 1

More on Graph Traversals

Share this solution

Let GGG be a directed graph and TTT a depth first search (DFS) spanning tree in GGG that is rooted at a vertex vvv. Suppose TTT is also a breadth first search (BFS) tree in GGG, rooted at vvv. Which of the following statements is/are TRUE for every such graph GGG and tree TTT ?

Step-by-step verified solution

Check you can still solve Graph Traversals under a clock

More from GATE CSE 2024 Set 1

More on Graph Traversals

Share this solution

Let $G$ be a directed graph and $T$ a depth first search (DFS) spanning tree in $G$ that is rooted at a vertex $v$ . Suppose $T$ is also a breadth first search (BFS) tree in $G$ , rooted at $v$ . Which of the following statements is/are TRUE for every such graph $G$ and tree $T$ ?

Let $G$ be a directed graph and $T$ a depth first search (DFS) spanning tree in $G$ that is rooted at a vertex $v$ . Suppose $T$ is also a breadth first search (BFS) tree in $G$ , rooted at $v$ . Which of the following statements is/are TRUE for every such graph $G$ and tree $T$ ?