Given a graph $G$ with $n$ vertices and $k$ connected components, show that the maximum number of edges is ${n - k + 1 \choose 2} $

Question

I am trying to prove the question I wrote in the title. I realized that the maximum number of edges is the maximal value of $ {a_1\choose 2} + ... + {a_k \choose 2}$ such that $a_i \geq 1$ for all $i$ and $a_1+...+a_k = n$.
But now I don't know how to prove that the value of this is the needed one. I know it is reached when all of the $a_i$'s are $1$ except one which is $n-k+1$ but I don't know how to prove this is the maximal case. I have tried induction but it just got to messy.

Answer 1

What happens to the number of edges when one point is moved from a small group to a larger group ? So replace $a_1,a_2$ with $a_1-1,a_2+1$.

Answer 2

Since the graph has k connected componenets, let each of them have n_i vertices ∀ i ∈ [1, k] Also Σn_i = n Max Edges in each component having n_i vertices = (n_i)(n_i -1)/2 so Total edges in k components , let say E will be as given below:

E = Σ(n_i)(n_i - 1) / 2

E = (Σ(n_i²) - n) / 2 Lets consider this equation 1

Now since we know that Σ(n_i) = n
Σ(n_i - 1) = n - k (On Subtracting k from both sides)
(Σ(n_i - 1))² = (n - k)² (On squaring both sides)
Σ(n_i - 1)² + Other Positive Terms = (n - k)²
Σ(n_i² + 1 - 2n_i) + C = n² + k² - 2nk
Σ(n_i²) + k - 2n + C = n² + k² - 2nk
Σ(n_i²) + C = n² + k² - 2nk + 2n - k
Σ(n_i²) + C = n² -k(2n - k) + 1(2n - k)
Σ(n_i²) + C = n² + (1 - k)(2n - k)
Σ(n_i²) + C = n² - (k - 1)(2n - k)
Σ(n_i²) ≤ n² - (k - 1)(2n - k) as C > 0

After plugging this result into equation 1 and simpifying we get:-
E = (Σ(n_i²) - n) / 2 ≤ (n² - (k - 1)(2n - k) - n)/2
On Simplyfing, we get
E ≤ ( (n - k)² + (n - k) )/2
E ≤ (n - k)(n - k + 1)/2