2
$\begingroup$

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.

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

Consider the disjoint union
$$ 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$.

$\endgroup$
1
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.