GATE CS 2018 Set 1 — Question 40

Statement (I): In a Depth First Search (DFS) of an undirected graph, there are only two types of edges: tree edges and back edges. A tree edge is an edge in the DFS tree itself. A back edge is an edge $(u, v)$ connecting a vertex $u$ to an ancestor $v$ in the DFS tree. There are no forward edges (connecting a vertex to a non-child descendant) or cross edges (connecting vertices in different subtrees that are not in an ancestor-descendant relationship). This is because if a cross edge $(u, v)$ existed, where $v$ is in a different, already visited subtree, the edge $(v, u)$ would have been explored when visiting $v$, and $u$ would have become a descendant of $v$, which contradicts the definition of a cross edge. Therefore, for any simple undirected graph, there are no cross edges with respect to a DFS tree. Statement (I) is true.Statement (II): In a Breadth First Search (BFS) of a graph, for any edge $(u, v)$, the depths of $u$ and $v$ in the BFS tree can differ by at most 1. That is, $|depth(u) - depth(v)| \le 1$. The statement claims that for every edge, the difference is exactly 1, i.e., $|i-j|=1$. This is not necessarily true. An edge can connect two vertices at the same level.
Consider a counterexample: a complete graph on 3 vertices (a triangle), $K_3$, with vertices ${A, B, C}$. Let the BFS start at vertex A.
Level 0: {A}
Level 1: {B, C}
The edge $(B, C)$ is an edge in the graph G. The depth of B is $i=1$ and the depth of C is $j=1$. For this edge, $|i-j| = |1-1| = 0$. This contradicts the statement that $|i-j|=1$ for every edge. Therefore, Statement (II) is false.Since only statement (I) is necessarily true, the correct option is (A).