Let 𝐺 be a directed graph and 𝑇 a depth first search (DFS) spanning tree in…

Key insight: a BFS tree records shortest-path distances (levels) from the root, so any edge between an ancestor and a descendant is tightly constrained by those levels.

• No forward-edges: If there were an edge from an ancestor u to a descendant w, the edge gives a path of length depth[u]+1 to w, so BFS forces depth[w] ≤ depth[u]+1. Since w is strictly deeper than u, depth[w] = depth[u]+1, so u must be the parent of w in T. Hence any ancestor→descendant edge is a tree edge, so non-tree forward-edges cannot occur.

• Back-edges can exist: For example, tree edges v → a → b together with an extra edge b → v form a back-edge. Levels remain 0,1,2 so T is still a BFS tree and a DFS that follows the tree edges produces the same DFS tree.

• Cross-edges can exist: For example, tree edges v → a and v → b plus an extra edge a → b. By choosing a DFS ordering that visits b before a, the DFS tree can be the same as the BFS tree (v is parent of both a and b) while a → b is classified as a cross-edge.

Conclusion: The only statement that must hold for every such G and T is that there are no forward-edges (non-tree ancestor→descendant edges).