For which n does $\displaystyle K_n$ have an Euler path but not an Euler circuit?

Printable View

- May 19th 2010, 05:23 PMmelodyEuler path and Euler circuit problem
For which n does $\displaystyle K_n$ have an Euler path but not an Euler circuit?

- May 19th 2010, 08:18 PMXianThere can be but one...
Excluding the trivial edgeless case of $\displaystyle K_1$ we can proceed as follows:

__If n is odd__

Then $\displaystyle K_n$ has all even degrees, and so by a theorem of Euler's we have that there exist an Eulerian circuit, which by technicality admits an Eulerian path (a circuit is a kind of path).

__If n is even__

Well clearly $\displaystyle K_2$ contains an Eulerian path but not an Euler circuit. However for all even n>2 we know that they have more than 2 vertices of odd degree (for $\displaystyle K_n$ we have all vertices with degree n-1). For there to be an Eulerian path, we can have at MAX two vertices of odd degree, and for even n>2, this condition fails. And so $\displaystyle K_2$ is the only graph the has an Eulerian path but no circuit.

For more info on Eulerian paths and circuits check out How can we tell if a graph has an Euler path or circuit?