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$?

Improve this question
$\endgroup$
  • $\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 Sep 29 '14 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$ – Thomas Kwon Sep 29 '14 at 10:50
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?

Improve this answer
$\endgroup$
  • $\begingroup$ Okay. I will try it. Thanks a lot. $\endgroup$ – Thomas Kwon Sep 29 '14 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$.

Improve this answer
$\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.