6
$\begingroup$

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.

  • 0
    @Salahuddin: A component is a maximal connected subgraph of a graph.2012-11-04

3 Answers 3

7

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

  • 0
    Thanks. Hasty thinking from my side.2012-10-22
4

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

-1

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

  • 2
    This is already explained better in two other answers given nearly 2 weeks ago.2012-11-04