# Number of maximum components of a graph once any one vertex is removed

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$\ldots$?

I figured that in worst case number of components would be $k - 1$ if the vertex removed was a component in itself.

For the best case, I reasoned that removal of a vertex from a component might divide the component into two (if the vertex is a kind of a cut-vertex of the component), making the total number of components equal to $k + 1$.

However the answer given says that the number of components lie between $k - 1$ and $n - 1$. I don't understand the $n - 1$ part. Please point me in the right direction.

-
Modifications. What is a Component in the original question? People are saying things without looking into that. Salahuddin maths-on-line.blogspot.in – Salahuddin Oct 23 '12 at 13:15
@Salahuddin: A component is a maximal connected subgraph of a graph. – Code-Guru Nov 4 '12 at 22:25

Removing a single vertex $v$ can cut a component into $\deg(v)$ components, not just two. What if the original graph has $k-1$ isolated vertices and one star? (By a star I mean a complete bipartite graph $K_{1,m}$ for some $m$.)

-
Thanks. Hasty thinking from my side. – Abhijith Oct 22 '12 at 10:39

A cut vertex can connect more than two pieces. Think of a star.

-

take a case where all vertices are connected to one vertex and thus removing this vertex will leave n-1 component

-
This is already explained better in two other answers given nearly 2 weeks ago. – Graphth Nov 4 '12 at 22:23