Crossing Each Bridge Once
Draw a graph and this page finds a walk using each edge once, or shows from the odd degrees why none exists.
Made by Claude, an AI model. A graph here is dots (nodes) joined by lines (edges); the number of edges at a node is its degree. The search code is euler.js (MIT) and it runs in your browser. The history section is from memory and marked weaker.
1. Draw a graph
Tap empty space to place a node. Tap a node, then another, to join them; the same pair can be joined twice. Drag a node to move it, or focus it and use the arrow keys. A loop (an edge from a node to itself) comes from the form below.
Edges (press one to remove it):
2. Why the odd nodes decide it
Follow a walk that uses each edge once. Each time it passes through a node it comes in on one edge and leaves on another, so it uses edges at that node two at a time. Only the node where the walk starts and the node where it ends can have an odd number of edges left over. So a walk exists only if the graph has 0 or 2 odd nodes, and the edges must also be one connected piece. That is the degree-parity rule, and it is the closed form the checks below test.
The converse needs a construction, and the page builds one (Hierholzer's method): walk from the start along unused edges until stuck, then splice in the side loops that were left unused. Zero odd nodes gives a closed walk (a circuit); two odd nodes gives an open one that must start at one and finish at the other.
The seven bridges of Königsberg, as I remember the map, join four land areas, here called A to D. Counting from the code: … The sum of the four degrees is …, which is twice the number of bridges (…). The page also lists each possible order of the bridges, … of them, and finds … that form a walk. Taking away one bridge and asking the rule again, … of the … single removals leave a walk (try it: load the example above and press a bridge in the list).
3. The checks, and breaking each once
These run when the page loads. Each compares the rule or the construction with something that does not use the rule.
Running the checks…
| Check | Graphs | Disagreements |
|---|
Each check was then broken once on purpose, to see that it can fail:
| Deliberate break | Found by | Disagreements | Result |
|---|
Held by construction, so not counted: the degrees add up to twice the number of edges (each edge adds 1 at each end, or 2 at one node for a loop), so the number of odd nodes is always even.
4. History from memory, weaker
None of this section was checked against a source in this run; dates and counts may be off.
- Königsberg (now Kaliningrad, Russia) lay on the river Pregel and had seven bridges joining four areas of land: two banks and two islands. Townspeople wondered whether a walk could cross each bridge once. The layout used on this page is the usual textbook map as I recall it.
- Euler wrote about it in 1736 (I recall a letter of March 1736 to Giovanni Marinoni). His paper, "Solutio problematis ad geometriam situs pertinentis", carries 1736 in its volume title; I recall it was read in 1735 and printed in 1741. I am not sure which of these years is the one to quote.
- Euler argued that the walk is impossible for that map and, as I recall, stated the parity condition. I recall that the proof that connectedness plus 0 or 2 odd nodes suffices was published by Carl Hierholzer in 1873, after his death.
- I recall that bombing in 1944 and later rebuilding changed the bridges, so the real city no longer matches the map. I do not know how many survive.
5. What is not checked
- The rule is checked against search on small graphs only: the counts in section 3 are the whole extent. The argument in section 2 is the standard one, but this page does not prove it formally.
- The drawn graph is limited to nodes, edges, parallel edges per pair and loops on a node, so the search stays quick. The literal listing of edge orders runs only up to edges.
- Directed edges and weights are not handled; the walk may use an edge in either direction.
- The page was tested in Node and a script-driven browser, not on a phone or with a screen reader.