Euler Tour Algorithm¶

Definition¶

For a connected undirected Euler network, the course's Euler tour algorithm starts at a vertex $s$, follows unused edges until returning to $s$, and calls the resulting cycle $\Omega$. If unused edges remain, choose a vertex $v$ on $\Omega$ incident to an unused edge, build another closed unused-edge traversal $\Omega_1$ from $v$, and splice $\Omega_1$ into $\Omega$ at $v$. Repeat until every edge is used.

Interpretation¶

The method builds a complete tour from smaller cycles: walk along unused edges until you are back at the start, then insert further closed detours at vertices already on the tour. Even degree ensures that every such detour can close at its starting vertex.

Starting at $s=A$$A$, the first cycle $\Omega=A-B-C-A$ (blue edges 1 to 3) returns to $A$ but leaves $A-D$$D$, $D-E$ and $E-A$ unused. The second cycle $A-D-E-A$ (red edges 4 to 6) starts at $A$, a vertex of $\Omega$, and is spliced in there, giving $A-B-C-A-D-E-A$$A$, which uses all six edges.

A walk can only get stuck at its start. When it arrives at a vertex $v\ne s$$s$, it has used an odd number of the edges at $v$, two for each earlier pass and one for this arrival; since the degree of $v$ is even, an unused edge remains to leave by. A closed walk uses an even number of edges at every vertex, so after removing its edges all remaining degrees are still even and the next detour also closes. Connectedness ensures that, as long as unused edges remain, one of them touches a vertex already on the tour.

The algorithm thus proves the harder half of the Euler network characterization: even degrees suffice. It is also the final step of the Chinese postman problem, where each duplicated copy counts as a separate edge.

Key Results¶

• Keep track of used edge identities, especially with parallel copies.
• The splice inserts one closed excursion into another without losing any previously used edge.
• Arbitrary eligible choices can give different valid Euler tours.

Examples¶

In the figure, the first cycle is $\Omega=A-B-C-A$$A$. The remaining cycle $A-D-E-A$ is spliced at $A$, giving $A-B-C-A-D-E-A$$A$. The even-degree condition permits these closed excursions.

• The worked example begins its first cycle at A.
• It later adds a cycle through B and then one through D to include all 12 edges.

Prerequisites¶

• Euler Network Characterization
• Cycle

Related Concepts¶

• Chinese Postman Problem

Sources¶

• OR Modelling · Week 4

Aliases: Hierholzer's algorithm Symbols: omega

Last updated: 20 October 2026 03:02