1,529 views
0 votes
0 votes

 

Let G be a simple graph with 20 vertices and 8 components. If we delete a vertex in G, then number of components in G should lie between ____.

(A) 8 and 20
(B) 8 and 19
(C) 7 and 19
(D) 7 and 20

 

Answer is (C) but i think also possible (B). anyone explain?

1 Answer

1 votes
1 votes
If a vertex is removed from the graph G, 2 cases are possible-

Case 1: remove 1 isolated vertex and you will left with 7 components.

case 2: just think, 1 vertex connected to 12 other vertices in a star form and other 7 vertices are isolated. now remove star vertex, and you will left with 12+7=19 vertices which are isolated, so 19 components.

So, option C.

Related questions

0 votes
0 votes
1 answer
1
sup739 asked Feb 18
133 views
Is Vector Subspace, Span, Basis, Dimension part of the gate CSE engineering mathematics linear algebra syllabus ?
0 votes
0 votes
1 answer
2
Dknights asked Sep 12, 2023
217 views
is this correct DFA ?