Lesson 182
Eulerian Paths
Hierholzer's Algorithm
1:00How to determine whether a graph can be traversed edge-by-edge in a single walk — and how to build that walk efficiently with Hierholzer's algorithm.
By the end, you can
- Explain the Königsberg bridge problem and why Euler's graph abstraction solved it.
- Define Eulerian path and Eulerian circuit, and state the difference.
- Apply the degree-parity rule to determine whether a connected graph has an Eulerian circuit, an Eulerian path, or neither.
- Identify the odd-degree vertices in a small graph and verify using the Handshaking Lemma.
- Trace Hierholzer's algorithm on a small graph, including the walk-and-splice step.
- State the time complexity of Hierholzer's algorithm and explain why it is O(E).
- Extend the existence conditions to directed graphs (in-degree vs. out-degree balance).
- Describe one real-world problem solved using Eulerian path theory.
Up next in Algorithms & Graph Algorithms
