Odd Order Complete Graph is Eulerian

Theorem

Let $K_n$ be the complete graph of $n$ vertices.

Then $K_n$ is Eulerian iff $n$ is odd.

If $n$ is even, then $K_n$ is traversable iff $n = 2$.

Proof

From the definition, the complete graph $K_n$ is $n-1$-regular.

That is, every vertex of $K_n$ is of degree $n-1$.

Suppose $n$ is odd. Then $n-1$ is even, and so $K_n$ is Eulerian.

Suppose $n$ is even. Then $n-1$ is odd.

Hence for $n \ge 4$, $K_n$ has more than $2$ odd vertices and so can not be traversable, let alone Eulerian.

If $n = 2$, then $K_n$ consists solely of two odd vertices (of degree $1$).

Hence, by Condition for Graph to be Traversable (or trivially, by inspection), $K_2$ has a Eulerian path, and so is traversable (although not Eulerian).

$\blacksquare$

Note

This was noted in 1809 by Louis Poinsot, who was unaware of Euler's more general result.

The remarkable point is that he gave an ingenious method for finding such a Eulerian circuit, which is a far from trivial exercise even for modestly sized complete graphs, e.g. those for $n < 100$.