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

9,636 views

## 3 Answers

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