3
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ A graph need not have any edges. What conditions are on the graph? $\endgroup$ – Matt Samuel Dec 6 '14 at 16:53
  • $\begingroup$ 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. $\endgroup$ – Timmy Dec 6 '14 at 16:57
3
$\begingroup$

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

$\endgroup$
2
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ 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? $\endgroup$ – Timmy Dec 6 '14 at 17:01
  • 1
    $\begingroup$ 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$. $\endgroup$ – Phicar Dec 6 '14 at 17:03
  • $\begingroup$ 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? $\endgroup$ – Timmy Dec 6 '14 at 17:07
  • $\begingroup$ Yes! That is your inductive step, you must see the equality i post in my answer..I do not understand your equation. $\endgroup$ – Phicar Dec 6 '14 at 23:31
1
$\begingroup$

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.

$\endgroup$
0
$\begingroup$

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

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