# In complete graph, how can I prove ${n\choose 2} = {k\choose 2} + k(n-k) + {n-k\choose 2}$ for $0 \le k \le n$

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

• 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? – Casteels Sep 29 '14 at 10:34
• yes i know that a complete graph with m vertices has C(m, 2) but, I don't know that how can prove it. – Thomas Kwon Sep 29 '14 at 10:50

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