Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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|improve this question
    
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

3 Answers 3

up vote 6 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|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|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|improve this answer
2  
This is already explained better in two other answers given nearly 2 weeks ago. –  Graphth Nov 4 '12 at 22:23

Your Answer

 
discard

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.