GATE CS 2003 Q8 — Graphs: Connectivity, Matching, Colouring

Let $G$ be a graph with $n$ vertices and $k$ components. Let $v$ be the vertex that is removed from $G$. We want to find the bounds on the number of components in the resulting graph $G' = G - \{v\}$.

1. Lower Bound (Minimum Components)

The number of components is minimized when the removed vertex $v$ is an isolated vertex (i.e., a component of size 1). Removing $v$ completely eliminates this component, while the remaining $k-1$ components are left unaffected.

Since removing a single vertex can destroy at most one component, the minimum number of components in $G'$ is:

2. Upper Bound (Maximum Components)

Suppose $v$ belongs to a component $C$ containing $m$ vertices. Removing $v$ can split the remaining $m-1$ vertices of $C$ into at most $m-1$ separate components (where each remaining vertex becomes isolated).

The other $k-1$ components of $G$ remain unaffected. Thus, the maximum number of components in $G'$ is:

To maximize this expression, we maximize $m$. Since $G$ has $n$ vertices and $k$ components, the largest possible component can have at most $n - (k - 1)$ vertices (which occurs when the other $k-1$ components are isolated vertices of size 1). Substituting $m \le n - k + 1$ into the expression:

Thus, the number of components in the resultant graph must necessarily lie between $k-1$ and $n-1$.