Maximal number of edges in a graph with $n$ vertices and $p$ components

Question

A graph with $n$ vertices and $p$ components has at least $n-p$ edges. Can I give an upper bound for the number of edges of such a graph? If so, how to prove it?

My attempt:

For each component, we have that the number of edges $m_i$ is given by $m_i \le \binom{n_i}{2}$, with $n_i$ the number of vertices within a component. So $m \le \sum_{i=1}^p \binom{n_i}{2} \le p\binom{n}{2}$.

Thanks.

Answer 1

The maximum occurs when $p-1$ of the components are singletons, so the number of edges is $\binom{n-p+1}{2}$.

Proof: Since the problem is finite, it suffices to show the maximum doesn't lie elsewhere. We may assume WLOG each component is a complete graph. If the maximum occurs with at least 2 nontrivial components, then move one vertex from the smaller (if equal just pick one) to the larger would increase the number of edges, contradiction. QED.