Question

We define D-Tree(G) as the tree obtained by applying the DFS algorithm on a graph G.
Consider the following statements regarding the same.

$S_1$ : If G is an undirected graph, then every edge in D-Tree (G) is either a tree edge or a back edge.

$S_2$ : If G is a undirected graph, then every edge in D-Tree(G) is either a tree edge, or a cross edge.

Which of the above statements are true ?

• A. $\text{Both}{S}_1\text{and}{S}_2$
• B. $\text{Only}{S}_2$
• C. $\text{Only}{S}_1$
• D. None of these

Answer 1

The correct option is C $\text{Only}{S}_1$

DFS of an undirected graph contains tree edges and back edges, but can never contain forward edges and cross edges.
$\text{Hence}{S}_1\text{is the only true statement.}$