yog/property/eulerian

Eulerian path and circuit algorithms using Hierholzer’s algorithm.

An Eulerian path visits every edge exactly once. An Eulerian circuit visits every edge exactly once and returns to the start. These problems originated from the famous Seven Bridges of Königsberg solved by Leonhard Euler in 1736, founding graph theory.

Algorithms

Key Concepts

• Eulerian Circuit: Closed walk using every edge exactly once
• Eulerian Path: Open walk using every edge exactly once
• Eulerian Graph: Graph with an Eulerian circuit
• Semi-Eulerian Graph: Graph with an Eulerian path but no circuit

Necessary and Sufficient Conditions

Undirected Graphs:

• Circuit: All vertices have even degree, connected (ignoring isolates)
• Path: Exactly 0 or 2 vertices have odd degree, connected

Directed Graphs:

• Circuit: In-degree = Out-degree for all vertices, weakly connected
• Path: At most one vertex has (out - in) = 1 (start), at most one has (in - out) = 1 (end), all others balanced

Hierholzer’s Algorithm

1. Start from any vertex (or odd-degree vertex for path)
2. Follow unused edges until returning to start (forming a cycle)
3. If unused edges remain, find vertex on current path with unused edges
4. Form another cycle from that vertex and splice into main path
5. Repeat until all edges used

Relationship to Other Problems

• Chinese Postman: Find shortest closed walk using every edge at least once (adds duplicate edges to make graph Eulerian)
• Route Inspection: Variant allowing non-closed walks
• Hamiltonian Path: Visits every vertex once (much harder, NP-complete)

Use Cases

• Route planning: Garbage collection, snow plowing, mail delivery
• DNA sequencing: Constructing genomes from overlapping fragments
• Circuit board drilling: Optimizing drill paths for PCB manufacturing
• Layout printing: Efficient pen plotting without lifting
• Museum guard tours: Covering all corridors efficiently

History

In 1736, Leonhard Euler proved that the Seven Bridges of Königsberg problem had no solution, establishing the conditions for Eulerian paths and founding graph theory as a mathematical discipline.

References

• Wikipedia: Eulerian Path
• Wikipedia: Seven Bridges of Königsberg
• Wikipedia: Hierholzer’s Algorithm
• Wikipedia: Route Inspection Problem
• CP-Algorithms: Eulerian Path

pub fn find_eulerian_circuit(
  graph: model.Graph(n, e),
) -> option.Option(List(Int))

pub fn find_eulerian_path(
  graph: model.Graph(n, e),
) -> option.Option(List(Int))

pub fn has_eulerian_circuit(graph: model.Graph(n, e)) -> Bool

pub fn has_eulerian_path(graph: model.Graph(n, e)) -> Bool