Given an undirected graph, denote N as the number of vertices and E as the number of edges in the Graph. The Graph consists of k connected components where k <= N.
- Assuming each connected component is complete, What is the minimum number of edges in G (as a function of N and k)?
The desired graph $G$ is a disjoint union of complete graphs $K_{n_1}, K_{n_2}, \dots, K_{n_k}$. Component $i$ has $n_i$ nodes and $\binom{n_i}{2}$ edges, so the problem is to find positive integers $n_1,n_2,\dots,n_k$ to minimize $$\sum_{i=1}^k \binom{n_i}{2}$$ subject to $$\sum_{i=1}^k n_i = N.$$ For example, if $k=1$, then $n_1=N$, and $G$ has $\binom{N}{2}$ edges. As another extreme example, if $k=N$, then $n_i=1$ for all $i$, and $G$ has $0$ edges. If $k=2$, what values for $n_1$ and $n_2$ minimize the number of edges?