GATE Computer Science (CS) 2018 Shift 1 Solved Paper

© examsiri.com
Question : 44 of 65
 
Marks: +1, -0
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 is 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?
Go to Question: