# How to relate combinatorial proof to bipartite graphs?

The question is - Let $k \geq 1$ be an integer and consider a sequence $n_1,n_2,\cdots,n_k$ of positive integers. Use a combinatorial proof to show that

$\binom{n_1}{2} + \binom{n_2}{2} +\cdots+ \binom{n_k}{2} \leq \binom{n_1+n_2+\cdots+n_k}{2}$

How can i prove this without using induction?

Additionally, For each $i$ with $1 \leq i \leq k$,consider the complete graph on $n_i$ vertices. How many edges does this graph have?

I thought of making graphs and figuring out a relation but still wasnt able to.

• The complete graph on $n$ verticies has $\binom{n}{2}$ edges. – Donald Splutterwit Sep 30 '17 at 19:14

$$G=K_{n_1}+\dotsb+K_{n_k}.$$ The LHS counts the number of edges in $G$. But $G$ is also a subgraph of $$H=K_{n_1+\dotsb+n_k}.$$ The RHS counts the number of edges in $H$.
Consider the number of edges on the complete graph with $n_1+n_2+\cdots +n_k$ verticies and the graph with $k$ components with the $i^{th}$ component consisting of a complete graph with $n_i$ verticies.