in Graph Theory edited by
15,141 views
65 votes
65 votes

Let $\text{G}$ be an arbitrary graph with $n$ nodes and $k$ components. If a vertex is removed from $\text{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
15.1k 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...😁

3
3

5 Answers

94 votes
94 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
18 votes
18 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.
1
1
11 votes
11 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$

edited by

3 Comments

Crystal clear explanation.
1
1
thank you
1
1
Really love these type of explanation. thank you
0
0
0 votes
0 votes

Let us consider there are k components in a graph with isolated vertices as well.

Now if we remove an isolated vertex it will result in k-1 components which is the least

If isolated vertices are not allowed in out graph with k components.Then in the worst case we will have components with 2 nodes and an edge between them so even if we remove the edge it wont change the number of components  

Now consider a start graph with n nodes in it.If we remove the innermost node will,it will take edges also along with its removal and we are left with n-1 vertices which are disconnected.

So the range is k-1≤no of components≤n-1 if isolated vertex is allowed

else  k≤ no of components ≤ n-1 if isolated vertices aren’t allowed.Correct answer option C.

Answer:

Related questions

Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true