Q. 62 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 ∣i − j∣ = 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
Answer: (A)
Explanation:
