Let T be a depth first search tree in an undirected graph G. Vertices u and n…

GATE · 2006 · CS

1. A.

   There must exist a vertex w adjacent to both u and n in G

2. B.

   There must exist a vertex w whose removal disconnects u and n in G

3. C.

   There must exist a cycle in G containing u and n

4. D.

   There must exist a cycle in G containing u and all its neighbours in G.

Attempted by 146 students.

The worked solution is available to enrolled students.

Video solution available to enrolled students.