Question

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 \)?

• A. There are no back-edges in \( G \) with respect to the tree \( T \)
• B. There are no cross-edges in \( G \) with respect to the tree \( T \)
• C. There are no forward-edges in \( G \) with respect to the tree \( T \)
• D. The only edges in \( G \) are the edges in \( T \)

Hint:

Understanding edge classifications in DFS (tree, back, forward, cross) is crucial to analyzing tree structures in directed graphs.

Answer 1

The Correct Option is C

Step 1: Analyze properties of DFS and BFS trees.
Option (1): Back-edges are present in a DFS tree if cycles exist in \( G \). However, for \( T \) to be both a DFS and BFS tree, back-edges cannot exist. Hence, this is FALSE as it depends on the structure of \( G \).
Option (2): Cross-edges appear in DFS when visiting previously visited vertices in another branch. In a BFS, no cross-edges exist by definition. However, the dual nature of \( T \) does not guarantee this universally. Hence, this is FALSE.
Option (3): Forward-edges are edges from a vertex to its descendant in DFS but not part of the DFS tree. Since \( T \) is both a DFS and BFS tree, forward-edges cannot exist. This is TRUE.
Option (4): The existence of \( T \) as both DFS and BFS does not limit \( G \) to contain only tree edges. Non-tree edges (e.g., cross or back-edges) may still exist. Hence, this is FALSE. Final Answer: \[ \boxed{(3)} \]