Euler Tour¶

Definition¶

An Euler tour is a closed traversal of a network that uses every edge exactly once. Vertices may be revisited. A network possessing an Euler tour is called an Euler network.

Interpretation¶

An Euler tour is a round trip that uses every edge exactly once. It models a route that must cover every street, for a postman or a street sweeper, without retracing any edge.

A network of two triangles sharing the vertex A, with the edges numbered 1 to 6 in the order of an Euler tour that uses every edge once and returns to A.

The numbers give the order of the edges in the tour $A-B-C-A-D-E-A$ $A$ . All six edges are used once and the tour ends where it started. The vertex $A$ , of degree 4, is passed through halfway as well, while each other vertex, of degree 2, is passed through once.

The requirement concerns edges, not vertices: vertices may be revisited, as $A$ is here. A round trip that visits every vertex exactly once is a different question; in the network of the figure no such trip exists, since a round trip through both triangles must pass through $A$ twice.

Whether an Euler tour exists is decided by the vertex degrees: a connected undirected network has one if and only if every vertex has even degree, by the Euler network characterization, and the Euler tour algorithm builds one by joining cycles. The network of the Königsberg bridges fails this test. When no Euler tour exists, the Chinese postman problem asks for a shortest closed route that uses every edge at least once.

Key Results¶

At each vertex, arrivals and departures balance.
For connected undirected networks, an Euler tour exists exactly when every vertex has even degree.
In a weighted Euler network, every Euler tour has length equal to the sum of all edge lengths.

Examples¶

In the illustrated Euler network, $\deg A=4$ and every other degree is 2. The tour returns to its start while using every edge once.

The Königsberg bridge network has no Euler tour because its vertices have odd degree.
The course weighted Euler example has total edge length 24, so its Euler tours have length 24.

Prerequisites¶

Sources¶

OR Modelling · Week 4

Aliases: Eulerian circuit, Euler circuit, Eulerian tour, Eulerian cycle, Euler cycle

Last updated: 20 October 2026 03:02