Q48

MCQ2 marks, −0.5

Let $T$ be a depth first search tree in an undirected graph $G$ . Vertices $u$ and $ν$ are leaves of this tree $T$ . The degrees of both $u$ and $ν$ 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 $ν$ in $G$

(B)

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

(C)

There must exist a cycle in $G$ containing $u$ and $ν$

(D)

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

Loading…