Multiple choice

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?

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

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

  3. There must exist a cycle in G containing u and n.

  4. There must exist a cycle in G containing u and all its neighbours in G.
Reveal answer Fill a bubble to check yourself
A Correct answer
Explanation

Keep practicing — related questions