Multiple choice

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

  1. k and n

  2. k - 1 and k + 1

  3. k - 1 and n - 1

  4. k + 1 and n - k
Reveal answer Fill a bubble to check yourself
D Correct answer
Explanation

When a vertex is removed from a graph with k components, the minimum number of resulting components is k-1 (when removing an isolated vertex). The maximum is k+1 (when removing a vertex that was part of a connected component, splitting it into two). Removing a vertex cannot reduce components by more than 1 or increase by more than 1.

Keep practicing — related questions