Let T be a depth first search tree in an undirected graph G. Vertices u and n…
2006
Let T be a depth first search tree in an undirected graph G. Vertices u and n are leaves of this tree T. The degrees of both u and n in G are at least 2. which one of the following statements is true?
- A.
There must exist a vertex w adjacent to both u and n in G
- B.
There must exist a vertex w whose removal disconnects u and n in G
- C.
There must exist a cycle in G containing u and n
- D.
There must exist a cycle in G containing u and all its neighbours in G.
Attempted by 79 students.
Show answer & explanation
Correct answer: D
Answer: There must exist a cycle in G containing u and all its neighbours in G.
Key observation: In an undirected DFS, every non-tree edge connects a vertex to one of its ancestors.
Because u is a leaf of the DFS tree, its only tree neighbour is its parent p; every other neighbour of u in G must be an ancestor of u.
Let a be the neighbour of u that is highest (closest to the root) on the ancestor chain. The tree path from a down to p contains every other ancestor-neighbour of u (they all lie between a and p on that chain).
The edges u–a and u–p together with the tree path from a to p form a single cycle that passes through u and every neighbour of u.
Therefore the given statement is true: there must exist a cycle containing u and all its neighbours.
Remarks on the other choices:
No vertex adjacent to both leaves is guaranteed; the two leaves can have back edges to different ancestors.
No single articulation vertex separating the two leaves is guaranteed; they might lie in the same biconnected component.
While each leaf with degree at least 2 lies on a cycle, the two leaves need not lie on the same cycle.
A video solution is available for this question — log in and enroll to watch it.