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 down between A. k and n B. k-1 and k+1 C. k-1 and n-1 D. k+1 and n-k
GATE 2003 · Discrete Mathematics · Graph Connectivity · medium
Answer: The component count lies between k-1 and n-1, which is option C.
- Lower bound: deleting an isolated vertex: If v is an isolated vertex in its own component, removing it deletes that component entirely and touches no other, so the count drops to k-1. You can never lose more than one component by deleting a single vertex.
- Upper bound: deleting a hub: If v is adjacent to all other vertices in a single component (like a star centre) and those vertices have no other edges, removing v leaves n-1 isolated vertices, giving n-1 components. With only n-1 vertices left, you can have at most n-1 components.
- Combine the bounds: Both extremes are attainable, so the number of components after one deletion lies between k-1 and n-1.