Question

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

• A. k and n
• B. k - 1 and k + 1
• C. k - 1 and n - 1
• D. k + 1 and n - k

Answer 1

The correct option is C k - 1 and n - 1

Maximum components will result after remove of a node if graph G is a star graph as shown below.

or a null graph of n vertices as shown below.

In either case, if node v is removed, the number of components will be n - 1, where n is the total number of nodes in the star graph.

$\therefore n-1$ is the maximum number of components possible. Minimum components will result if the node being removed is a lone vertex in which case, the number of components will be k - 1.

$\therefore$ The number of components must necessary lie between k - 1 and n - 1.