Graph with $k$ components.

Question

Let $G$ be a simple graph on $n$ vertices. If $G$ has $k$ components and every component is complete prove that: $$|E| \le \frac{(n-k)(n-k+1)}{2}$$ I'm asking for advice.

Answer 1

If the graph has $k$ components of size $n_1, n_2, \dots, n_k$ then it has $\displaystyle \frac{n_1(n_1-1)}{2} + \frac{n_2(n_2-1)}{2} + \dots + \frac{n_k(n_k-1)}{2} = \frac{1}{2}(\sum n_i^2 - n)$ edges.

Now, can you bound $\sum n_i^2$ under the constraint that $\sum n_i = n$?

Answer 2

Hint: In other words, you have to prove that, if $x_1,\dots,x_k$ are positive integers such that $x_1+\cdots+x_k=n$, then $$\binom{x_1}2+\cdots+\binom{x_k}2\le\binom{n-k+1}2.$$ In other words, you want to know that the sum $$\binom{x_1}2+\cdots+\binom{x_k}2$$ is maximized (subject to the given constraints, i.e., positive integers adding up to $n$) when $x_1=\cdots=x_{k-1}=1$ and $x_k=n-k+1$.

We may as well assume that $x_1\le\cdots\le x_k$. The problem is trivial if $k=1$, so let's say $k\ge2$. Now, supposing $x_1\gt1$, what happens to the sum if we change $x_1$ to $x_1-1$ and $x_k$ to $x_k+1$? Does it get bigger or smaller?