Let G be an arbitrary graph with n nodes and k components. If a vertex is…
2003
Let G be an arbitrary graph with n nodes and k components. If a vertex is removed from G, the number of components in the resultant graph must necessarily lie between
- A.
k and n
- B.
k - 1 and k + 1
- C.
k - 1 and n - 1
- D.
k + 1 and n - k
Attempted by 103 students.
Show answer & explanation
Correct answer: C
Answer: k - 1 and n - 1
Reasoning:
Lower bound (k - 1): If the removed vertex is an isolated vertex (a component by itself), removing it reduces the total number of components by exactly 1. No removal can delete more than one component at once, so the number of components cannot fall below k - 1.
Upper bound (n - 1): Let the component containing the removed vertex have m vertices. After removing that vertex, that component can split into at most m - 1 components (for example, removing the center vertex of a star yields m - 1 isolated vertices). The new total number of components is then k - 1 + (m - 1) = k + m - 2.
To maximize k + m - 2, take the largest possible m. The largest m occurs when all other components are single vertices, so m = n - (k - 1). Substituting gives k + (n - k + 1) - 2 = n - 1. Hence the number of components after removing one vertex cannot exceed n - 1.
Conclusion: After removing one vertex from G the number of components lies between k - 1 and n - 1, inclusive.