GATE CS 2018 Q.40 (CS Q.30): Graph Traversals, Topological Sort and Connectivity

Let $G$ be a simple undirected graph. Let $T_D$ be a depth first search tree of $G$ . Let $T_B$ be a breadth first search tree of $G$ . Consider the following statements.

(I) No edge of $G$ is a cross edge with respect to $T_D$ . (A cross edge in $G$ is between two nodes neither of which is an ancestor of the other in $T_D$ .)
(II) For every edge $(u,v)$ of $G$ , if $u$ is at depth $i$ and $v$ is at depth $j$ in $T_B$ , then $|i - j| = 1$ .

Which of the statements above must necessarily be true?

I only

II only

Both I and II

Neither I nor II

Official answer and solution

Official answer: A
From: Official GATE 2018 answer key

Solution

Review structural properties of edge types in DFS and BFS trees of undirected graphs.

Analyze Statement I:

In a DFS traversal of an undirected graph, every edge of $G$ is either a tree edge (part of the DFS tree) or a back edge (connecting a vertex to an ancestor in the DFS tree).
There are no cross edges (edges between subtrees with no ancestor-descendant relationship) in an undirected DFS tree.
Thus, statement I is necessarily true.

Analyze Statement II:

In a BFS traversal of an undirected graph, an edge $(u, v)$ can connect vertices at depths $i$ and $j$ where $|i - j| \le 1$ .
Specifically, an edge may exist between two vertices at the same depth, in which case $i = j$ and $|i - j| = 0$ (for example, in a triangle graph $K_3$ , two non-root vertices are both at depth 1 and connected by an edge).
Since $|i - j|$ can be 0, it is not necessarily equal to 1. Statement II is false.

Therefore, only statement I must necessarily be true, matching option A.

Final answer

The answer is the one in the official GATE answer key. The solution is this site's own explanation.

Source

Paper: GATE 2018 Computer Science and Information Technology (CS)
Question: 40 of 65, printed as CS Q.30
Section: Computer Science and Information Technology

Report an error in this question

GATE questions are the work of the organising institutes. This site is independent and is not affiliated with them.

Question

Solution

Source