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
Nice explanation for this question :
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).
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 ?
is it true that lies between k-1 and n-1 include k-1 and [email protected] Danish& Arjun sir
This will help ...
Option C ...
Gatecse