Eulerian Trail

An Eulerian Trail is a continuous path in a finite graph that visits every edge exactly once, while an Eulerian Circuit (or Eulerian Cycle) is a trail that starts and ends on the same vertex. According to Euler's theorems, an undirected connected graph containing no isolated vertices has an Eulerian Circuit if and only if every vertex has an even degree. It has an open Eulerian Trail if exactly two vertices have an odd degree. This module visualizes Hierholzer's algorithm to construct such trails by identifying unused edges and merging cycles.

Experiment

You can interactively run this algorithm in the Eulerian Trail module.

1. Set the Vertex count to 5.
2. Enter the following into the Edges textarea to form two connected triangles (0-1-2-0 and 0-3-4-0):
   0 1
   1 2
   0 2
   0 3
   3 4
   0 4
3. Click the Finish button.
4. Observe that the status shows Circuit, with 6 consumed edges. The final trace correctly shows the trail visiting all edges and returning to the start vertex.