1
$\begingroup$

I'm studying graphs in algorithm and complexity, but I'm not very good at math. How can I prove that ${n\choose 2} = {k\choose 2} + k(n-k) + {n-k\choose 2}$ for $0 \le k \le n$?

$\endgroup$
2
  • $\begingroup$ Do you understand why a complete graph with $m$ vertices has ${m\choose 2}$ edges? also, I think you mean $k(n-k)$ in that middle term, no? $\endgroup$
    – Casteels
    Commented Sep 29, 2014 at 10:34
  • $\begingroup$ yes i know that a complete graph with m vertices has C(m, 2) but, I don't know that how can prove it. $\endgroup$ Commented Sep 29, 2014 at 10:50

2 Answers 2

4
$\begingroup$

Hint: Consider a complete graph on $n$ vertices and partition its vertex set in two subsets, one with $k$ and one with $n-k$ elements. How many edges does the graph have in total? How many are there within each of the two subsets? Can you finish off the argument?

$\endgroup$
1
  • $\begingroup$ Okay. I will try it. Thanks a lot. $\endgroup$ Commented Sep 29, 2014 at 10:57
1
$\begingroup$

Let $\{1,\ldots,n\}$ be partitioned into two sets $A$ and $B$, where $A=\{1,\ldots,k\}$ and $B = \{k+1,\ldots,n\}$. In how many ways can we choose two elements from $\{1,\ldots,n\}$? There are three possibilities: both elements are from $A$ (the two elements can be chosen in ${k \choose 2}$ ways), both elements are from $B$, or one element is from $A$ and the other element is from $B$.

$\endgroup$

You must log in to answer this question.

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