# Biggest number of components in a graph?

What is the biggest number of components in a graph that has 14 vertices and 44 edges?

Since total degree of all vertices in a graph equals to 2 * number of edges, I calculated that for 44 edges, 14 vertices together must have 88 degrees. 88 / 14 = 6, therefore each of them would have to be connected to other 6 vertices and we would still have 4 edges left. So, the only solution I see is using a full graph K10, where we'd have 90 edges ((n*(n-1))/2). We'd use 10 vertices and eliminate 2 edges. And the rest 4 vertices we would leave isolated, so we'd get 5 components all together.

• Try turning your intuition to a proof. Dec 1, 2017 at 16:05
• Is my intuition even correct? I don't know how to turn it into a proof.. Dec 2, 2017 at 11:23
• The way to check whether your intuition is correct is via proof. Dec 2, 2017 at 15:03
• Could you give me an example or a hint as to how to formulate the proof? Dec 3, 2017 at 8:44
• Try solving some similar problems with smaller numbers, and see if you can generalize. Dec 3, 2017 at 12:27

Suppose that a graph having $n$ vertices and $m$ edges consists of $k$ connected components, say of sizes $n_1,\ldots,n_k$. Then $$m \leq \binom{n_1}{2} + \cdots + \binom{n_k}{2}.$$ Conversely, given $n_1,\ldots,n_k$ summing to $n$ which satisfy this inequality, we can construct a graph with $n$ vertices, $m$ edges, and at least $k$ connected components. We conclude that the maximum number of connected components of a graph with $n$ vertices and $m$ edges is the maximal $k$ such that we can find $n_1,\ldots,n_k \geq 1$ summing to $n$ satisfying the inequality above.
This leads to the following question: given $k$, maximize $\binom{n_1}{2} + \cdots + \binom{n_k}{2}$ subject to the constraint that $n_1,\ldots,n_k \geq 1$ are integers summing to $n$. The key is the following observation: $$\binom{a+1}{2} + \binom{b-1}{2} - \binom{a}{2} - \binom{b}{2} = a-b+1.$$ This shows that as long as $n_i \geq n_j$, moving a vertex from $n_j$ to $n_i$ increases $\binom{n_i}{2} + \binom{n_j}{2}$. It follows that the choice of $n_1,\ldots,n_k$ maximizing $\binom{n_1}{2} + \cdots + \binom{n_k}{2}$ is $n_1=n-k+1$, $n_2=\cdots=n_k=1$.
We have proved: the maximal number of connected components of a graph with $n$ vertices and $m$ edges is the maximal $k$ such that $$m \leq \binom{n-k+1}{2}.$$