Question

Let G be an arbitrary graph with v nodes and k components. If a vertex is removed from G, the number of components in the resultant graph must necessarily lie down between _____ and _____

(a) n-1 and n+1

(b) v and k

(c) k+1 and v-k

(d) k-1 and v-1

The question was posed to me in an interview.

My question is taken from Complete and Connected Graphs topic in section Graphs of Discrete Mathematics

Answer 1

Right option is (d) k-1 and v-1

Explanation: If a vertex is removed from the graph, lower bound: number of components decreased by one = k-1 (remove an isolated vertex which was a component) and upper bound: number of components = v-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 (v-1) vertices isolated making (v-1) components.