GATE 2018 CS Q.30: solution and answer

GATE 2018 · CSQ.30 · 2 marks · MCQ

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?

(A)
I only
(B)
II only
(C)
Both I and II
(D)
Neither I nor II

See the question in the paper

Tap to open full size

Answer and solution

ANSWER

(A) I only

Official answer: ASource: Official answer key, GATE 2018 CS (IIT Guwahati)

Statement I is a standard property of DFS on undirected graphs: because every edge is bidirectional, whenever DFS is about to traverse an edge (u,v) to an already-visited vertex v, that v must still be on the current recursion stack (i.e., an ancestor of u in T_D) — otherwise v's own DFS call would already have explored into u through this same edge before u could be discovered independently, a contradiction. So undirected DFS never produces cross edges (only tree edges and back edges). Hence Statement I is always true, for every simple undirected graph G and every DFS tree T_D of it.
Statement II claims every edge of G joins two vertices whose T_B-depths differ by exactly 1. Consider the counterexample G = a triangle on vertices a, b, c (each pair adjacent). Running BFS from a: depth(a) = 0, and both b and c are direct neighbours of a, so depth(b) = depth(c) = 1.
The edge (b,c) is present in G (it is one side of the triangle), and |depth(b) - depth(c)| = |1-1| = 0, not 1. So Statement II fails for this graph — it is not necessarily true.
Since Statement I always holds and Statement II can be violated, the statement(s) that must necessarily be true is 'I only', which is option (A).

KEY IDEA

In an undirected graph, DFS never produces cross edges (only tree edges and back edges), so Statement I always holds; but BFS trees can have non-tree edges joining two vertices at the same level (e.g. any odd cycle such as a triangle), so Statement II can fail.

WATCH OUT FOR

Assuming BFS tree edges are the only edges of G and forgetting that non-tree ("cross") edges of an undirected graph can join two vertices at the same BFS depth — exactly what breaks Statement II.

From the GATE 2018 CS paper. Every question of this paper · Download the full paper · All 28 Graph algorithms questions, with notes

GATE 2018 CS Q.30: solution and answer

Answer and solution

More Graph algorithms questions