- 0 odd vertices: a circuit, from any vertex back to it
- 2 odd vertices: a path from one to the other
- 4 or more: impossible in one stroke
Euler path finder
Can you draw the house of Santa Claus without lifting your pencil and without going over a line twice? You can, but only if you start at one of the two bottom corners, and there are 44 ways from each. The reason is the degree of a vertex, the number of lines that meet there: every time the pencil passes through a vertex it uses two of its lines. Leonhard Euler found this rule in 1736 with the seven bridges of Königsberg. Trace a figure yourself, see where you get stuck and why, ask for a hint, or watch an algorithm draw it. Pick a figure and trace it: tap a vertex to start, then tap the edges or the next vertices in order, or drag from vertex to vertex. Each edge may be used only once. Back takes back a step, Hint shows the next safe edge, and Solve plays Fleury's or Hierholzer's algorithm step by step. Odd vertices are filled, and the badge on each vertex is its degree. Under Draw, tap empty space to add a vertex and tap two vertices to join them, again for a second edge between them; drag a vertex to move it. Erase removes vertices and edges. When more than two vertices are odd, Add puts in the edges that make the figure drawable.
How it works
- Pick a figure, such as the seven bridges of Königsberg, the house of Santa Claus or a star, or draw your own under Draw, with as many edges between two vertices as you like.
- Tap a vertex to start, then tap the edges or the vertices in order, or drag from vertex to vertex. If you get stuck, the status line says why; Back takes back a step and Hint shows a safe next edge.
- Read the degree rule under the board, add the edges it suggests to an impossible figure, or press Solve to watch Fleury's or Hierholzer's algorithm draw it step by step.
Why the odd vertices decide it
A stroke that passes through a vertex arrives along one line and leaves along another, so it uses the lines at that vertex two at a time. Only where the stroke starts or ends can a line be left without a partner. So a vertex with an odd number of lines must be the start or the end. With no odd vertex, the stroke ends where it began: an Euler circuit. With two, it runs from one to the other: an Euler path. With four or more, there are too many ends for one stroke, and k odd vertices need k/2 strokes. Königsberg had four land masses, with five, three, three and three bridges: all four odd, so no walk could cross each bridge once. One new bridge between two of them would have made the walk possible.
Fleury's and Hierholzer's algorithms
Knowing that a figure can be drawn is not the same as drawing it: a careless stroke can cut itself off from the lines it still needs. Fleury's algorithm of 1883 avoids that with one rule: never cross a bridge, a line whose removal would split the lines left into two pieces, unless there is no other line. Hierholzer's algorithm, from a paper published in 1873, is faster: walk anywhere until you get stuck, which can only happen back at the start, then from a vertex on the tour that still has free lines walk another closed loop and splice it into the tour. It takes time in proportion to the number of edges, and it is how computers find Euler paths.
Frequently asked questions
What is the difference between an Euler path and an Euler circuit?
Both use every edge of a graph exactly once. An Euler circuit ends where it started; an Euler path ends somewhere else. A connected graph has a circuit when every vertex has an even degree, and a path when exactly two vertices have an odd degree, in which case the path runs from one of them to the other.
Why can't the seven bridges of Königsberg be crossed once each?
Draw each land mass as a vertex and each bridge as an edge. The Kneiphof island had five bridges and the other three land masses three each, so all four vertices are odd. A walk can only start or end at an odd vertex, and four are too many. Adding one bridge between two of them leaves two odd vertices, and the walk becomes possible.
How many ways are there to draw the house of Santa Claus?
44 from each of the two bottom corners, 88 in all, counting a different order or direction as a different way. From any other vertex it cannot be done, because the bottom corners are the only two with an odd number of lines. The app counts the ways for small figures this way.
What is a bridge in a graph?
An edge whose removal splits a connected graph into two pieces. Fleury's algorithm never crosses a bridge of the edges still left unless it has no other choice, because crossing it would leave part of the figure behind. In this app, a stroke that gets stuck after crossing a bridge too early is told which step it was.
Can there be more than one edge between two vertices?
Yes. A graph with parallel edges is called a multigraph, and Königsberg needs one: two bridges joined the Kneiphof to each bank. Under Draw, tap two vertices again to add another edge between them, up to four. The degree rule works the same way, counting every edge.
Ready to try it?
Open PictorX in your browser — no install, no credit card required to start.
Go to Editor