Complete Graph is Hamiltonian for Order Greater than 2

From ProofWiki
Jump to navigation Jump to search

Theorem

Let $n \in \Z$ be an integer such that $n > 2$.

Let $K_n$ denote the complete graph of order $n$.


Then $K_n$ is Hamiltonian.


Proof

First we note that when $n = 2$ there is one edge in $K_n$.

So if you start at one vertex $u$ and travel along that edge to the other vertex $v$, you cannot return to $u$ except by using that same edge.

Consequently $K_2$ is not Hamiltonian.

$\Box$


Let $n = 4$.

Let us take two vertices $u, v$ of $K_n$:


From Complete Graph is Regular, the degrees of $u$ and $v$ are given by:

$\map \deg u = \map \deg v = n - 1$

Let us remove the edge $u v$ which joins them.

Let the resulting graph be denoted $G$.

We now have that:

$\map \deg u = \map \deg v = n - 2$

From Ore's Theorem, $G$ is Hamiltonian if for each pair of non-adjacent vertices $u, v \in V$:

$\deg u + \deg v \ge n$

In $G$, we have that:

Hence:

\(\ds \deg u + \deg v\) \(=\) \(\ds 2 \paren {n - 2}\)
\(\ds \) \(=\) \(\ds n + \paren {n - 4}\)
\(\ds \) \(\ge\) \(\ds n\) as $n \ge 4$

Thus $G$ is Hamiltonian.

A Hamiltonian graph with another edge added is still Hamiltonian.

Thus restoring the edge $u v$ to $G$ to turn it back into $K_n$ means that $K_n$ is Hamiltonian.

$\Box$


When $n = 3$ we cannot use this theorem, as you then find for the resulting $G$:

$\deg u + \deg v = 2$

which is less than $3$.

Instead we inspect the complete graph $K_3$ and see it is is the cycle graph $C_3$

K3.png

The result follows from Cycle Graph is Hamiltonian.

$\blacksquare$