Let G be an undirected graph. Consider a depth-first traversal of G, and let T…
GATE · 2000 · CS · Question 2 subparts
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 statements 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
Attempted by 214 students.
Show answer
Correct answer: C
The worked solution is available to enrolled students.
Video solution available to enrolled students.
Explore the full course: Iocl Engineers Officers Grade A Paper 2