Course contentsShow
← Mathematics
Lesson 2681 of 3,12153. Graph TheoryFree lesson

Finding Eulerian Paths and Circuits: Algorithms

Learn Hierholzer's algorithm and techniques to construct Eulerian paths and circuits when they exist.

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:

  1. Start at any vertex and follow edges to form a circuit (always possible due to even degrees), marking edges as used.
  2. If unused edges remain, find a vertex on your current circuit that has unused edges.
  3. From that vertex, form a new circuit using only unused edges.
  4. Splice this new circuit into the original circuit at that vertex.
  5. 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.