For which n does 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 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 we can proceed as follows:

__If n is odd__

Then 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 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 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 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?