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

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.