Let \(G\) be a directed graph and \(T\) a depth first search (DFS) spanning tree in \(G\) that is rooted at a vertex \(v\). Suppose \(T\) is also a breadth first search (BFS) tree in \(G\), rooted at \(v\). Which of the following statements is/are TRUE for every such graph \(G\) and tree \(T\) ?
Answer
(C)
Explanation
In a BFS tree the depth of every vertex equals its shortest distance from \(v\), and any edge \((u, w)\) forces \(\text{dist}(w) \le \text{dist}(u) + 1\).
- C is true. A forward edge \((u, w)\) leads to a descendant \(w\) of \(u\) that is not its child, so \(w\) is at least two levels below \(u\) in \(T\). The edge itself gives \(\text{dist}(w) \le \text{dist}(u) + 1\), a contradiction.
- A and D are false: with the edges \(v \to u\) and \(u \to v\), both searches give the tree \(v \to u\), and \(u \to v\) is a back edge.
- B is false: with the edges \(v \to a\), \(v \to b\) and \(b \to a\), a DFS that visits \(a\) first builds the tree \(v \to a\), \(v \to b\), which is also the BFS tree, and \(b \to a\) is a cross edge.
Answer: C