Let G be an arbitrary graph with n nodes and k components. If a vertex is…
2009
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
Attempted by 51 students.
Show answer & explanation
Correct answer: C
When a vertex is removed from a graph with n nodes and k components, the number of components can decrease by at most one if the removed vertex was an isolated component (lower bound: k-1). Conversely, removing a critical articulation point can split a connected component into multiple parts. In the worst-case scenario, such as removing the center of a star graph with n nodes, the result can be up to n-1 isolated components. Therefore, the number of components in the resultant graph necessarily lies between k-1 and n-1 inclusive.