GATE CS 2018 Q30 — Graph Traversals (BFS, DFS)

We analyze the two statements for a simple undirected graph $G$:

Statement I: In a Depth First Search (DFS) of an undirected graph, every edge of $G$ is classified as either a tree edge or a back edge. If there is an edge $(u, v)$ in $G$, the vertex visited first (say $u$) must complete its exploration only after all its reachable descendants (including $v$) are explored. Thus, one vertex must be an ancestor of the other, meaning there are no cross edges. Hence, Statement I is true.

Statement II: In a Breadth First Search (BFS) tree $T_B$, the depth difference between two adjacent vertices $u$ and $v$ in $G$ can be at most $1$, i.e., $|i - j| \le 1$. It is possible that $|i - j| = 0$ (i.e., they are at the same depth).
For example, consider a triangle graph $K_3$ with vertices $\{A, B, C\}$. If we start BFS from $A$ (depth $0$), both $B$ and $C$ will be at depth $1$. The edge $(B, C)$ connects two vertices at the same depth, so $|1 - 1| = 0 \neq 1$. Hence, Statement II is false.

Thus, only Statement I is necessarily true.