A simple graph ( a graph without parallel edge or loops) with n vertices and k…
2009
A simple graph ( a graph without parallel edge or loops) with n vertices and k components can have at most
- A.
n edges
- B.
n-k edges
- C.
(n − k)(n − k + 1) edges
- D.
(n − k)(n − k + 1)/2 edges
Attempted by 54 students.
Show answer & explanation
Correct answer: D
To maximize the number of edges in a simple graph with n vertices and k components, one component should contain as many vertices as possible while the remaining k-1 components contain exactly 1 vertex each (isolated vertices). This leaves n - (k - 1) = n - k + 1 vertices for the main component. The maximum number of edges occurs when this main component is a complete graph K_{n-k+1}. The number of edges in a complete graph with m vertices is m(m-1)/2. Substituting m = n - k + 1, the maximum number of edges is (n - k + 1)(n - k)/2.