GATE CS 2024 Set 1 — Question 45

MSQ+2 / -0HardDFS Edge ClassificationGraph AlgorithmsAlgorithmsBFS TraversalGraphs (Data Structure)Programming & Data Structures

Algorithms → Graph Algorithms → BFS Traversal

Last updated 20 August 2026

Question

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

There are no back-edges in

G

with respect to the tree

T

There are no cross-edges in

G

with respect to the tree

T

There are no forward-edges in

G

with respect to the tree

T

The only edges in

G

are the edges in

T

Correct answer

Solution

Let

T

be a spanning tree of

G

rooted at

v

. We are given that

T

is both a DFS tree and a BFS tree.

Analysis of Edge Types:

1.Forward Edges: A forward edge

(u, w)

in a DFS tree connects a node

u

to a descendant

w

that is not its child. This implies that the path from

u

w

in the tree

T

has length

\ge 2

. Thus, in the tree

T

, the level of

w

is at least

level(u) + 2

However,

T

is also a BFS tree. A fundamental property of BFS is that for any edge

(x, y)

in the graph

G

, the level difference satisfies

level(y) \le level(x) + 1

. If there were a forward edge

(u, w)

G

, it would require

level(w) \le level(u) + 1

. This contradicts the tree structure requirement that

level(w) \ge level(u) + 2

. Therefore, no forward edges can exist.

2.Back Edges: A back edge connects a node to an ancestor. For example, a simple cycle

1 \to 2 \to 1

yields a tree

1 \to 2

which is both DFS and BFS, with

(2, 1)

being a back edge. Thus, statement (A) is false.

3.Cross Edges: A cross edge connects two nodes where neither is an ancestor of the other. Consider

V=\{1, 2, 3\}

with edges

(1, 3), (1, 2), (2, 3)

. If we visit 3 then 2 in DFS, the tree is edges

\{(1, 3), (1, 2)\}

. The edge

(2, 3)

is a cross edge (from 2 to the already visited 3). This same tree is a valid BFS tree (levels: 1 at 0; 2, 3 at 1). Thus, statement (B) is false.

4.Only Tree Edges: Since back and cross edges can exist, statement (D) is false.

Conclusion: Only statement (C) is always true.

GATE CS 2024 Set 1 — Question 45

Question

Correct answer

Solution

More questions on Graph Algorithms