Euler Paths and Circuits

Math for CS · Axiom Academy

Traversing every edge exactly once The Seven Bridges of Konigsberg In 1736, the citizens of Konigsberg (now Kaliningrad, Russia) posed a question: is it possible to walk through the city, crossing each of its seven bridges exactly once, and return to your starting point? Leonhard Euler modeled this as a graph problem — four landmasses as vertices, seven bridges as edges — and proved it was impossible. His reasoning launched the entire field of graph theory. Note the distinction from Hamiltonian paths (which visit every vertex once). Euler paths visit every edge once. Euler proved exact necessary and sufficient conditions. These are among the cleanest theorems in graph theory. If there are exactly 2 odd-degree vertices, the Euler path must start at one and end at the other. The intuition is straightforward: every time you enter a vertex, you must also leave it. If the walk passes through vertex v a total of k times, it uses k edges entering and k edges leaving, consuming 2k edges incident to v . For the walk to use all edges at v , the degree must be even. The two allowed odd-degree vertices in an Euler path are the start (one extra departure) and the end (one extra arrival). Finding Euler Circuits: Hierholzer's Algorithm Once we know an Euler circuit exists, we can find it efficiently in O(n + m) time using Hierholzer's algorithm (1873). Start at any vertex. Follow unused edges until you return to the start, forming a cycle C . If C uses all edges, you are done.

This is the written version of the interactive lesson above. See the full Math for CS course.