0
$\begingroup$

I'm studying graphs in algorithm and complexity, but I'm not very good at math. In a Complete graph, prove $ \sum n_{i} = n, then { n_{i} \choose 2 } \le { n \choose 2 } $ ? please give some ideas.

$\endgroup$

2 Answers 2

1
$\begingroup$

$$ \binom{n}{2}=\frac{n(n-1)}{2}=\sum_i\frac{n_i(n-1)}{2}\geq\sum_i\frac{n_i(n_i-1)}{2}=\sum_i\binom{n_i}{2}. $$

$\endgroup$
1
$\begingroup$

If $\sum n_i =n$ and the $n_i$'s are nonnegative, then $n_i \le n$ for all $i$, and so ${n_i \choose 2} \le {n \choose 2}$ for all $i$.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .