The GATE Grind

GATE 2018 CS – Question 40

Algorithms · Graph Algorithms: Traversals, Minimum Spanning Trees, Shortest Paths · 2 marks · Multiple choice

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?

  1. I only
  2. II only
  3. Both I and II
  4. Neither I nor II

Practise this question in The GATE Grind →

Show answer and explanation

Correct answer: (A) I only

Explanation

In an undirected graph every non-tree edge of a DFS tree connects an ancestor with a descendant, so there are no cross edges (I is true). In a BFS tree, an edge can join two vertices at the same depth (then $|i-j|=0$), so II is false.