Question-46

Consider an undirected graph G. Let T be a depth first search traversal tree. Let u be a vertex in G and let v be the next visited vertex after visiting u in the traversal. Which of the following statements is always true ?

• (u, v) must be an edge in G, and u is a descendant of v in T
• (u, v) must be an edge in G and v is a descendant of u in T
• If (u, v) is not an edge in G then u is a leaf in T
• If (u, v) is not an edge in G then u and v must have the same parent in T

Answer

• (u, v) must be an edge in G, and u is a descendant of v in T
• (u, v) must be an edge in G and v is a descendant of u in T
• If (u, v) is not an edge in G then u is a leaf in T
• If (u, v) is not an edge in G then u and v must have the same parent in T