number of edges induction proof

Question

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.

Answer 1

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.

Answer 2

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.

Answer 3

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