Main Page | See live article | Alphabetical index

Eulerian path

An Eulerian path (Euler walk) in a graph is a path that uses each edge precisely once. If such a path exists, the graph is called traversable.

An Eulerian cycle (Eulerian circuit, Euler tour) in a graph is a cycle with uses each edge precisely once. If such cycle exists, the graph is called Eulerian.

The name is after a famous mathematician Leonhard Euler, who stated and solved the problem of Seven Bridges of Königsberg in 1736, which is the first formally discussed problem in graph theory.

L.Euler showed that an Eulerian cycle exists if and only if all vertices in the graph are of even degree. An Eulerian path exists, if and only if at most two vertices in the graph are of odd degree.