Euler paths and circuits explained
Some figures can be drawn in one stroke, without lifting the pencil and without going over a line twice, and some cannot, however long you try. You do not have to try: count the lines at each corner. If no more than two corners have an odd number of lines, the figure can be drawn, and those corners are where the stroke must start and end. Leonhard Euler found this rule in 1736, and with it he founded graph theory.
The seven bridges of Königsberg
The Prussian city of Königsberg, today Kaliningrad, lay on both banks of the river Pregel and on two islands in it, the Kneiphof and the Lomse. Seven bridges joined the four parts: two from the Kneiphof to each bank, one between the two islands, and one from the Lomse to each bank. The townspeople wondered whether a walk could cross every bridge exactly once. Euler answered in a paper he presented to the Academy in St. Petersburg in 1735, printed in 1741: it cannot. His key step was to throw away everything but the parts of town and the bridges between them, which is what a graph does: a vertex for each land mass and an edge for each bridge, with two edges where two bridges join the same places.
The degree rule
The degree of a vertex is the number of edges at it. A stroke that passes through a vertex comes in along one edge and goes out along another, so it uses that vertex's edges in pairs. Only the first and the last vertex of the stroke can keep an edge without a partner. So a vertex of odd degree must be where the stroke starts or ends. The Kneiphof had five bridges and the other three parts three each: four odd vertices, two too many. In general a connected graph has an Euler circuit, a stroke that ends where it started, when every degree is even, and an Euler path when exactly two degrees are odd, from one of them to the other. The number of odd vertices is never one, or any other odd number: every edge adds 2 to the sum of all degrees, so the sum is even. Euler noticed this too, and it is now called the handshake lemma.
Why the rule is enough
Euler showed that a figure with more than two odd vertices cannot be drawn, and said, without proof, that every other connected figure can. The proof came from Carl Hierholzer, a German mathematician who died young in 1871; his paper appeared in 1873. Start at an odd vertex if there is one, otherwise anywhere, and walk along unused edges as long as you can. Because every other vertex has even degree, you can only get stuck at the end vertex. If edges are left, some of them touch the walk so far, because the figure is connected. From such a vertex, walk again until you get stuck, which now happens back at that vertex, and splice the loop into the walk there. Repeat until no edge is left. The proof is also the fastest algorithm: every edge is looked at a fixed number of times.
Fleury's algorithm: do not burn your bridges
A stroke can fail even on a figure that can be drawn. Take two triangles joined by a single edge and start at a corner of the first: if you cross to the second triangle before the first is finished, you can never come back. The joining edge is a bridge: removing it splits the figure in two. Fleury's algorithm of 1883 gives one rule: at each vertex, take an edge that is not a bridge of the edges still left, unless there is no other. Following it, you always finish. Testing for a bridge takes time, so Fleury's algorithm is slower than Hierholzer's, but it is the one you can follow with a pencil, and the hint in the app uses it.
Fixing a figure
A figure with k odd vertices needs k/2 strokes. To draw it in one, add edges that join odd vertices in pairs: each new edge makes two odd vertices even. Adding k/2 − 1 edges leaves two odd vertices and gives a path; adding k/2 leaves none and gives a circuit. One more bridge in Königsberg, between any two of the four parts, would have made the walk possible, and two would have made a round trip possible. History did something similar: two bridges were lost in the Second World War and two were replaced by a modern road, and the five bridges at the old places today can be crossed once each, from one island to the other.
Counting the ways
The house of Santa Claus, a square with both diagonals and a roof, is the German children's version of the puzzle: "Das ist das Haus vom Ni-ko-laus" has eight syllables, one for each line. Its two bottom corners are the only odd vertices, and there are exactly 44 ways to draw it from each of them, 88 in all. For directed graphs the number of Euler circuits has a formula, the BEST theorem, named after de Bruijn, van Aardenne-Ehrenfest, Smith and Tutte. For ordinary graphs no such formula is known, and counting is believed to be hard in general, so the app counts small figures by trying every way, skipping steps that would cut the figure in two.
Where Euler paths are used
A snowplough, a street sweeper or a postman wants to cover every street once and return. If every crossing has an even number of streets, an Euler circuit does it; otherwise some streets must be driven twice, and choosing the cheapest ones is the Chinese postman problem, posed by Meigu Guan in 1962. A pen plotter or a laser cutter saves time by drawing as many lines as possible without lifting. In genome sequencing, millions of short pieces of DNA are put together by finding an Euler path through a de Bruijn graph, in which every piece is an edge. And the same rule tells you which line drawings in a puzzle book are worth trying.
Explore it
Open the Euler Path Finder to trace twelve figures yourself, from Königsberg in 1736 and today to stars, nested squares and a cube, or draw your own with parallel edges. The odd vertices are filled, every vertex shows its degree, and the degree rule under the board says what is possible and which edges would fix the figure. If you get stuck, the app says whether you started at the wrong vertex or crossed a bridge too early, and at which step. Hint gives a safe next edge, and Solve draws the figure with Fleury's algorithm, showing the bridge test, or with Hierholzer's, showing each splice.
Frequently asked questions
Is an Euler path the same as a Hamiltonian path?
No. An Euler path uses every edge once and may visit a vertex many times; a Hamiltonian path visits every vertex once and need not use every edge. Whether a graph has an Euler path is answered at once by counting odd vertices, but no quick test is known for Hamiltonian paths, and finding one is one of the classic hard problems of computer science.
Does the degree rule work when two vertices are joined by more than one edge?
Yes. Every edge counts towards the degree of both of its ends, whether or not another edge joins the same two vertices. Königsberg is such a multigraph, with two bridges from the Kneiphof to each bank. An edge from a vertex to itself, a loop, adds 2 to its degree and never changes whether it is odd.
What about one-way streets?
In a directed graph each edge has a direction, and the rule compares the edges going in and out of each vertex. There is an Euler circuit when every vertex has as many edges in as out and the edges hang together, and an Euler path when one vertex has one more edge out than in, one has one more in than out, and all the others are balanced. The path then runs from the first to the second.
Can a figure with exactly one odd vertex exist?
No. The degrees of all vertices add up to twice the number of edges, because every edge has two ends. That sum is even, so the number of odd degrees in it must be even too: 0, 2, 4 and so on, never 1 or 3.
Ready to try it?
Open PictorX in your browser — no install, no credit card required to start.
Open the Euler Path Finder