Let G be a simple undirected graph. Let TD be a depth first search tree of G

Q. Let G be a simple undirected graph. Let TD be a depth first search tree of G. Let TB be a breadth first search tree of G.  Consider the following statements.

I . No edge of G is a cross edge with respect to TD. (A cross edge in G is between two nodes neither of which is an ancestor of the other in TD.)

II. For every edge (u,v) of G, if u is at depth i and v is at depth j in TB, then |𝑖 − 𝑗| = 1. Which of the statements above must necessarily be true?

(A) I only                                                       (B) II only

(C) Both I and II                                            (D) Neither I nor II

Ans: I only

Sol:

Undirected graph cant have cross edges in DFS forest. Hence statement 1 is TRUE. Using triangle graph we can counter the second statement.