Question 45

Let $d(u)$ denote the depth (distance from the root $v$) of vertex $u$ in the spanning tree $T$. Since $T$ is a BFS tree of $G$ rooted at $v$, every directed edge $(x, y)$ in $G$ must satisfy:

• Forward-edges (C): With respect to the DFS tree $T$, a forward-edge $(x, y)$ is a non-tree edge from an ancestor $x$ to a proper descendant $y$, which means $d(y) \ge d(x) + 2$. This contradicts the BFS property $d(y) \le d(x) + 1$. Hence there can be no forward-edges in $G$ with respect to $T$, so (C) is TRUE.
• Back-edges (A) and Cross-edges (B): A back-edge goes from a descendant $x$ to an ancestor $y$ ($d(y) \le d(x) \le d(x) + 1$), and a cross-edge between two children of $v$ has $d(y) = d(x) = 1 \le d(x) + 1$. Both are compatible with $T$ being both a DFS tree and a BFS tree, so (A), (B), and (D) are FALSE.