The maximum number of possible edges in an undirected graph with n vertices and k components is ______.

GATE 1991 · Discrete Mathematics · Graph Connectivity · medium

Answer: Maximum edges = C(n-k+1, 2) = (n-k+1)(n-k)/2.

1. Allocate vertices optimally: Optimal: k-1 isolated-vertex components (0 edges each), one component with n-k+1 vertices as a complete graph. Splitting vertices between components always loses edges since C(a+b,2) > C(a,2)+C(b,2) for a,b >= 1.
2. Count edges in the large clique: m = n-k+1 vertices: edges = C(n-k+1,2) = (n-k+1)(n-k)/2. Example: n=6, k=2 => C(5,2)=10 edges.