11,592 views

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 down between

1. $k$ and $n$
2. $k-1$ and $k+1$
3. $k-1$ and $n-1$
4. $k+1$ and $n-k$

### 1 comment

Suppose graph $G$$=$ $N_{n}$ (Null graph of n vertices)

then it has n vertices and n components too.

Now, remove 1 vertex then left with (k-1) components or (n-1) components.

Gives upper and lower bound both...😁

If a vertex is removed from the graph $G$,

Lower Bound: number of components decreased by one $= k - 1$ (remove an isolated vertex which was a component)

Upper Bound: number of components $= n-1$ (consider a vertex connected to all other vertices in a component as in a star and all other vertices outside this component being isolated. Now, removing the considered vertex makes all other $n-1$ vertices isolated making $n-1$ components)

Therefore (C).

by

For the upper bound are we thinking k = 1 , as a star graph with the middle vertex being connected to all others . Now when the middle vertex is removed from the graph then the number of components becomes n-1.
RANGE K-1 TO N-1 contains K also. minimum number of components can be K-1 if we delete a single isolated vertex i.e. vertex which is not connected to any other vertex.
why upper bound is not k+1 as n-1=k+1 if we remove a centre vertex in graph

Visualise from my explanation

You wont get anything better than this when you remove the highligted vertex, you will get the above two cases.

by

After deleting central vertices then all opponent getting same so i think it can't possible
After removing the central vertex from star graph the it becomes disconnected and becomes k-1 components. That's the upper bound and it's correct.

Visualizing the solution:-

Let a graph $G(6,4)$ be composed of a star graph and an isolated vertex. Here $n=6, k =2$ MAX CASE: REMOVE THE HUB ($C$)

If we remove a vertex, all its edges must also be removed. Now, we have $5 = n-1$ components

MIN CASE: REMOVE THE VERTEX ($F$):- Now we have only $’1’$ = $(k-1)$ component.

Hence, by the above example, we can see that the Answer is Option (C) $k-1$ and $n-1$

### 1 comment

Crystal clear explanation.
Lower bound k-1 ,upper bound n-k.
by

Because if u remove frm star graph it only has one compo so n-1 but the general case will be n-k for k compo graph.
But consider the case where the other components are isolated vertices.
Hello anshu , he is asking about maximum possible number of components , which would be n-1 and n-k is supposed to be lesser or equal to n-1.
yes when graph is star graph then components will be n-1 components will be come.