# 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 graph need not have any edges. What conditions are on the graph? – Matt Samuel Dec 6 '14 at 16:53
• The question is rather ambiguous, just says find an expression for # of edges in kn and then prove by induction. I'm assuming a complete graph, which requires edges. – Timmy Dec 6 '14 at 16:57

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

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.

• In order for a graph to be complete it doesn't necessarily have to have an additional vertices. Each distinct pair must be connected though. Why are you adding one? – Timmy Dec 6 '14 at 17:01
• Because if you have $K_n$, you can result with $K_{n+1}$ by adding a new vertex and all the edges between that new vertex and all the vertices you had in $K_n$. – Phicar Dec 6 '14 at 17:03
• OHHHH. That should be my inductive step then, correct? replace Kn-1 with (n-1)(n-2)/2 = n-2(n-2)/2 and then solve? – Timmy Dec 6 '14 at 17:07
• Yes! That is your inductive step, you must see the equality i post in my answer..I do not understand your equation. – Phicar Dec 6 '14 at 23:31

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.

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