Let 𝐺 be a simple undirected graph, 𝑇𝐷 be a DFS tree on 𝐺, and 𝑇𝐵 be the…
2020
Let 𝐺 be a simple undirected graph, 𝑇𝐷 be a DFS tree on 𝐺, and 𝑇𝐵 be the BFS tree on 𝐺. Consider the following statements.
Statement 𝐼: No edge of 𝐺 is a cross with respect to 𝑇𝐷
Statement 𝐼𝐼: For every edge (𝑢,𝑣) of 𝐺, if 𝑢 is at depth 𝑖 and 𝑣 is at depth 𝑗 in 𝑇𝐵 then ∣𝑖−𝑗∣=1
In the light of the above statements, choose the correct answer from the options given below
- A.
Both Statement 𝐼 and Statement 𝐼𝐼 are true
- B.
Both Statement 𝐼 and Statement 𝐼𝐼 are false
- C.
Statement 𝐼 is correct but Statement 𝐼𝐼 is false
- D.
Statement 𝐼 is incorrect but Statement 𝐼𝐼 is true
Attempted by 93 students.
Show answer & explanation
Correct answer: C
Answer: Statement I is true; Statement II is false.
Reasoning:
DFS on an undirected simple graph produces only tree edges and back edges. There are no cross edges in an undirected DFS.
BFS organizes vertices by distance from the root, so for any edge (u,v) the depths i and j satisfy |i - j| ≤ 1. Statement II claimed equality |i - j| = 1, which is stronger and not always true.
Counterexample to the claimed equality: take a root r with two neighbors a and b, and include an edge between a and b. In a BFS from r, both a and b are at depth 1, but edge (a,b) has |1 - 1| = 0, contradicting |i - j| = 1.
Conclusion: The correct assessment is that no cross edges appear in the DFS of an undirected graph (so the first statement is true), while the BFS property should be |i - j| ≤ 1 rather than equality (so the second statement is false).
A video solution is available for this question — log in and enroll to watch it.