Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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.

share|cite|improve this question
Modifications. What is a Component in the original question? People are saying things without looking into that. Salahuddin – 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
up vote 7 down vote accepted

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$.)

share|cite|improve this answer
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.

share|cite|improve this answer

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

share|cite|improve this answer
This is already explained better in two other answers given nearly 2 weeks ago. – Graphth Nov 4 '12 at 22:23

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.