Let {G} be a simple undirected graph. Let T_{D} be a depth first search tree of {G}. Let T_{B} be a breadth first search tree of G. Consider the following statements: I. No edge of {G} is a cross edge with respect to T_D. (A cross edge is {G} is between two nodes neither of which is an ancestor of the other in T_{D} ). II. For every edge (u, v) of G, if u is at depth i and v is at depth j in T_{B}, then (i-j)=1. Which of the statements above must necessarily be true?

Question

Let  {G} be a simple undirected graph. Let T_{D} be a depth first search tree of  {G}. Let T_{B} be a breadth first search tree of G. Consider the following statements:   I. No edge of  {G} is a cross edge with respect to T_D. (A cross edge is  {G} is between two nodes neither of which is an ancestor of the other in T_{D} ).   II. For every edge (u, v) of G, if u is at depth i and v is at depth j in T_{B}, then (i-j)=1.   Which of the statements above must necessarily be true?

Examsnet · Accepted Answer

Correct Answer is : Neither I nor II

GATE Computer Science (CS) 2018 Shift 1 Solved Paper