Q2.19

MCQ2 marks, −0.5

Let $G$ be an undirected graph. Consider a depth-first traversal of $G$ , and let $T$ be the resulting depth-first search tree. Let $u$ be a vertex in $G$ and let $v$ be the first new (unvisited) vertex visited after visiting $u$ in the traversal. Which of the following statement is always true?

(A)

$\{u, v\}$ must be an edge in $G$ , and $u$ is a descendant of $v$ in $T$

(B)

$\{u, v\}$ must be an edge in $G$ , and $v$ is a descendant of $u$ in $T$

(C)

If $\{u, v\}$ is not an edge in $G$ then $u$ is a leaf in $T$

(D)

If $\{u, v\}$ is not an edge in $G$ then $u$ and $v$ must have the same parent in $T$

Loading…