GATE CSE 2003 | Question: 8, ISRO2009-53
in Graph Theory edited by
9,636 views
50 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
9.6k views

Subscribe to GO Classes for GATE CSE 2022

3 Answers

73 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

6 Comments

in a completely connected graph, there is only one component, so after removing one vertex, the number of connected components still stay 1, so should it not be k to n-1 ?

1
We are talking about lower bound here.'k-1' is lesser than k and that's the lowest number of components possible.
7

is it true that lies between k-1 and n-1 include k-1 and [email protected] DanishArjun sir

0
@Arjun Sir lower bound will be 'K' if we remove one vertex here then component may not increase.
1
Upper bound is also possible when there are 0 edges..

I.e every vertex is a component.. So removal of a vertex means removing a component..

Hence after removal there are n-1 components
0
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
6 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.

 

1 comment

After deleting central vertices then all opponent getting same so i think it can't possible
0
–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
But consider the case where the other components are isolated vertices.
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.
0
yes when graph is star graph then components will be n-1 components will be come.
1
Answer:

Related questions

Ask
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