Using complete graphs and a combinatorial proof, show $\sum_{i=1}^{j}$ ${k_i}\choose{2} $ $\leq$ ${n}\choose{2}$

Question

Suppose we have a set of positive integers {${k_1, k_2, ... , k_j}$} such that $ \sum_{i=1}^{j} k_i = n $. Use a combinatorial proof to show $\sum_{i=1}^{j}$ ${k_i}\choose{2} $ $\leq$ ${n}\choose{2}$. Hint: Use complete graphs.

I know complete graphs have ${n}\choose{2}$ total edges as we know each vertex in a complete graph will be connected to $n-1$ total edges, and so to remove the duplicates we divide by 2, as in $n(n-1)/2$ total edges. How can we use this to show that it is greater than the LHS?

Answer 1

The interpretation of the $\{k_1, k_2, \dots, k_j\}$ is a partition of the vertices, so $\binom{k_i}2$ is the number of edges within that partition. Can you proceed from here?

Answer 2

Consider the graph made of $j$ connected components. The $i^{th}$ component being the complete graph with $k_i$ verticies. Now compare this graph with the connected graph on $n$ verticies.

By considering the number of edges the inequality follows.