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$ ?

Let $d(u)$ denote the shortest path distance from the root $v$ to any vertex $u$ in $G$. Since $T$ is a BFS tree rooted at $v$, for any vertex $u$, the tree-path distance from $v$ to $u$ in $T$ equals $d(u)$.

1. Forward-edges: A forward-edge in a DFS tree is a non-tree directed edge $(u, w)$ where $u$ is an ancestor of $w$ in $T$. Because $w$ is a proper descendant of $u$ and $(u, w)$ is not a tree edge, the distance in $T$ satisfies:

   $$d(w) \ge d(u) + 2$$

   However, if the directed edge $(u, w)$ exists in $G$, the triangle inequality for shortest path distances requires:

   $$d(w) \le d(u) + 1$$

   This is a contradiction. Therefore, no forward-edges can exist in $G$ with respect to tree $T$. Hence, statement (C) is TRUE.

2. Back-edges and Cross-edges: Back-edges go from a descendant to an ancestor (e.g., creating a directed cycle), which satisfies $d(w) \le d(u) + 1$ because $d(w) < d(u)$. Cross-edges can also satisfy the shortest path property. Thus, back-edges and cross-edges may exist, making (A), (B), and (D) false in general.

Hence, only C is correct.