edited by
15,202 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$
edited by

5 Answers

Best answer
94 votes
94 votes

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

 

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

55 votes
55 votes
6 answers
1
44 votes
44 votes
5 answers
2
8 votes
8 votes
3 answers
3
go_editor asked Jun 15, 2016
3,395 views
A simple graph ( a graph without parallel edge or loops) with $n$ vertices and $k$ components can have at most$n$ edges$n-k$ edges$(n-k) (n-k+1)$ edges$(n-k) (n-k+1)/2$ e...
7 votes
7 votes
3 answers
4
go_editor asked Jun 15, 2016
5,331 views
In a graph $\text{G}$ there is one and only one path between every pair of vertices then $\text{G}$ is aPathWalkTreeCircuit