Finding Eulerian Paths and Circuits: Algorithms
You'll learn how to systematically construct an Eulerian path or circuit when one exists, using Hierholzer's algorithm.
The Core Idea
Once you've determined that a graph has an Eulerian circuit or path (using Euler's theorem about vertex degrees), you need a practical way to actually build it. Hierholzer's algorithm does this efficiently by constructing cycles and merging them.
Think of it like exploring a maze where you must use every passage exactly once. Instead of randomly wandering, you follow a systematic strategy: walk until you complete a cycle back to your start, then "patch in" any unexplored loops you encounter along the way.
Hierholzer's Algorithm for Eulerian Circuits
Input: A connected graph with all vertices of even degree.
Steps:
- Start at any vertex and follow edges to form a circuit (always possible due to even degrees), marking edges as used.
- If unused edges remain, find a vertex on your current circuit that has unused edges.
- From that vertex, form a new circuit using only unused edges.
- Splice this new circuit into the original circuit at that vertex.
- Repeat steps 2–4 until all edges are used.
Result: An Eulerian circuit traversing every edge exactly once.
Modification for Eulerian Paths
For an Eulerian path (graph with exactly two odd-degree vertices):
- Start at one of the odd-degree vertices
- Follow the same cycle-building and merging process
- End at the other odd-degree vertex
Why It Works
Even-degree vertices guarantee you can always exit any vertex you enter (edges come in pairs). Building circuits ensures you never get stuck, and merging sub-circuits preserves the "use each edge once" property while covering the entire graph.
Key Takeaway: Hierholzer's algorithm efficiently constructs Eulerian paths and circuits by iteratively building and merging cycles, leveraging the degree conditions guaranteed by Euler's theorem.