1. One-Liner
An Eulerian circuit uses every edge exactly once and returns to the start; an Eulerian path exists under degree parity conditions; Hierholzer constructs it in O(E).
2. The Problem It Solves
Route inspection, drawing without lifting the pen, DNA sequencing superstrings (historical) — traverse all edges efficiently once.
3. The Core Idea
Undirected connected (ignoring isolates): Eulerian circuit iff all degrees even; path iff exactly two vertices odd degree (endpoints). Hierholzer stitches cycles along unused edges.
4. How It Works (Step-by-Step)
| Step | Action |
|---|---|
| 1 | Check degrees / connectivity |
| 2 | Start at odd vertex (path) or any (circuit) |
| 3 | Walk until stuck, push vertices, backtrack merging cycles |
| 4 | Reverse output trail |
5. Dry Run Example
Figure-eight graph: Eulerian circuit exists if all degrees even. Two odd vertices ⇒ open trail between them.
6. Key Properties
| Property | Value |
|---|---|
| Directed | in/out degree conditions differ |
| Semi-Eulerian | Path not circuit naming |
7. Where It Is Used
| Domain | Use |
|---|---|
| Logistics | Chinese Postman (related) |
| Bioinformatics | De Bruijn assembly ideas |
8. Interview Tips
State degree conditions clearly; implement multiset adjacency for edge removal.
9. Comparison with Other Algorithms
| Euler trail | Hamiltonian path | |
|---|---|---|
| Complexity | Polynomial | NP-hard |
10. Complexity
| -- | -- |
|---|---|
| Time | O(E) for Hierholzer |
| Space | O(E) |
Implementation Example (PYTHON)
def eulerian_circuit(adj):
# adj[u] = multiset of neighbors (mutable)
stack = [0]
path = []
while stack:
u = stack[-1]
if adj[u]:
v = adj[u].pop()
adj[v].remove(u)
stack.append(v)
else:
path.append(stack.pop())
return path[::-1]