Euler (1736): Seven Bridges of Königsberg. Eulerian circuit: traverse every edge once, return to start. Exists iff connected and all degrees even. Eulerian path: traverse every edge once. Exists iff connected and 0 or 2 odd-degree vertices.
How to Use
Select graph:
- Circuit: All even degrees
- Path: 0 or 2 odd
- Neither: >2 odd
Seven Bridges
Euler (1736) proved the Königsberg bridge problem has no solution: the graph has 4 odd-degree vertices, so no Eulerian path exists. This founded graph theory! The first theorem in the field.
Hierholzer's Algorithm
Find Eulerian circuit in O(m): (1) Start at any vertex, follow edges until returning. (2) If unused edges remain at a visited vertex, start a new circuit there. (3) Splice circuits together. Efficient and elegant.
Step-by-Step Instructions
- 1Select graph.
- 2Count odd degrees.
- 3Classify Euler.
- 4Find path/circuit.
- 5Verify traversal.