number of edges induction proof Proof by induction that the complete graph $K_{n}$ has $n(n-1)/2$ edges. 
I know how to do the induction step I'm just a little confused on what the left side of my equation should be. $E = n(n-1)/2$  It's been a while since I've done induction. I just need help determining both sides of the equation. 
 A: When $n=1$ we know that $K_1$ has no edges since ${1\choose 2}=0$. Assume the result is true for some $k\geq 2\in \mathbb{N}$, that is $K_k$ has ${k\choose 2}$ edges. Consider $K_{k+1}$. Deleting any vertex of $K_{k+1}$, say $x$, gives us $K_k$ since every vertex in $K_{k+1}$ has degree $k$. We know by the induction hypothesis that $K_k$ has ${k\choose 2}$ edges. So adding the vertex $x$ back we obtain $K_{k+1}$ which has ${k\choose 2}+k={k(k-1)\over 2}+k={k^2-k+2k\over 2}={k^2+k\over 2}={(k+1)k\over 2}={k+1\choose 2}$ edges. Thus by the Principle of Mathematical Induction $K_n$ contains ${n\choose 2}$.
A: I am not really sure about it, surely you meant the complete graph $K_n$. Suppose you have solved the $K_{n-1}$ case, so you have $\frac{(n-1)(n-2)}{2}$ edges, then you need to add one vertex, but because it is complete, you have to connect that vertex to all the others, so you are going to add $n-1$ edges, so you ended up with $|E(K_{n-1})|+n-1$.
So your equation is $|E(K_{n-1})|+n-1=|E(K_n)|$, and you are proving that $|E(K_n)|=\frac{n(n-1)}{2}$.
Hope it helps.
A: While an induction proof was requested, I will offer a couple of other combinatorial proofs so that alternative (and perhaps more straight-forward) approaches are present.
A complete graph on $n$ vertices is such that for all $x, y \in V(G)$, $\{x, y\} \in E(G)$. That is, all pairs of vertices are adjacent. So each vertex has degree $n-1$. By the Handshake Lemma, we get:
$$\sum_{i=1}^{n} (n-1) = 2E = n(n-1)$$
It follows that there are $\frac{n(n-1)}{2}$ edges.
Similarly, we note that since each pair of edges are adjacent, and an edge is a $2$-element subset of $V(G)$, then we are counting all possible two-element subsets of $V(G)$. Thus, there are $\binom{n}{2} = \frac{n(n-1)}{2}$ such edges.
A: $$ \textrm{Base Case: Let } n = 2 , E = \frac{2(2-1)}{2} = 1, \textrm{which is true} $$
$$IH: E = \frac{k(k-1)}{2}$$
$$IS: E = \frac{k+1(k)}{2} $$
$$   E = \frac{k(k-1)+2k}{2} $$
$$  E = \frac{k^2 - k }{2} $$
$$E = \frac{k(k-1)}{2} $$
