Given a graph $G$ with $n$ vertices and $k$ connected components, show that the maximum number of edges is ${n - k + 1 \choose 2} $ 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.
 A: 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$.
A: Since the graph has k connected componenets, let each of them have ni vertices  ∀ i ∈ [1, k]
Also  Σni = n
Max Edges in each component having ni vertices = (ni)(ni -1)/2
so Total edges in k components , let say E will be as given below:
E = Σ(ni)(ni - 1) / 2 
E = (Σ(ni2) - n) / 2  Lets consider this equation 1
Now since we know that
Σ(ni) = n 
Σ(ni - 1) = n - k (On Subtracting k from both sides)
(Σ(ni - 1))2 = (n - k)2 (On squaring both sides)
Σ(ni - 1)2 + Other Positive Terms = (n - k)2
Σ(ni2 + 1 - 2ni) + C = n2 + k2 - 2nk
Σ(ni2) + k - 2n + C = n2 + k2 - 2nk

Σ(ni2) + C = n2 + k2 - 2nk + 2n - k

Σ(ni2) + C = n2 -k(2n - k) + 1(2n - k)

Σ(ni2) + C = n2 + (1 - k)(2n - k)

Σ(ni2) + C = n2 - (k - 1)(2n - k)
Σ(ni2) ≤ n2 - (k - 1)(2n - k) as C > 0
 After plugging this result into equation 1
and simpifying we get:-

E = (Σ(ni2) - n) / 2 ≤ (n2 - (k - 1)(2n - k) - n)/2
On Simplyfing, we get 
E ≤ ( (n - k)2 + (n - k) )/2
 E ≤ (n - k)(n - k + 1)/2
