How many edges must be removed to produce the spanning forest of a graph with…
2013
How many edges must be removed to produce the spanning forest of a graph with N vertices, M edges and C connected components?
- A.
M + N − C
- B.
M − N − C
- C.
M − N + C
- D.
M + N + C
Attempted by 39 students.
Show answer & explanation
Correct answer: C
A spanning forest with N vertices and C components has exactly N - C edges. Subtracting this from the original M edges gives M - (N - C). This simplifies to M - N + C edges to remove.
A video solution is available for this question — log in and enroll to watch it.