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

Dark Mode

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

0

0

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

–3 votes

0

1