in Graph Theory edited by
11,592 views
53 votes
53 votes

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$
in Graph Theory edited by
11.6k views

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...😁

0
0

4 Answers

81 votes
81 votes
Best answer

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

edited by

4 Comments

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.
0
0
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.
0
0
why upper bound is not k+1 as n-1=k+1 if we remove a centre vertex in graph
0
0
7 votes
7 votes

Visualise from my explanation

You wont get anything better than this

 

when you remove the highligted vertex, you will get the above two cases.

 

2 Comments

After deleting central vertices then all opponent getting same so i think it can't possible
0
0
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.
0
0
2 votes
2 votes

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.
1
1
–3 votes
–3 votes
Lower bound k-1 ,upper bound n-k.
by

4 Comments

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.
0
0
But consider the case where the other components are isolated vertices.
2
2
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.
1
1
yes when graph is star graph then components will be n-1 components will be come.
1
1
Answer:

Related questions