In a depth-first traversal of a graph G with n vertices, k edges are marked as…
2005
In a depth-first traversal of a graph G with n vertices, k edges are marked as tree edges. The number of connected components in G is
- A.
k
- B.
k + 1
- C.
n - k - 1
- D.
n - k
Attempted by 96 students.
Show answer & explanation
Correct answer: D
Key idea: For each connected component with v vertices, a depth-first traversal produces v - 1 tree edges.
Derivation:
Let the graph have c connected components with sizes v1, v2, ..., vc.
Each component contributes vi - 1 tree edges, so the total number of tree edges is k = sum(vi - 1) = (sum vi) - c = n - c.
Rearrange to find the number of connected components: c = n - k.
Example: If n = 7 and DFS finds k = 4 tree edges, then the number of connected components is 7 - 4 = 3.