In the 1700s the Prussian city of Königsberg had a Sunday pastime: find a walk that crosses each of its seven bridges exactly once. Nobody managed it. Nobody could say why not either, until Leonhard Euler stopped looking at the bridges and started counting.
Königsberg (today Kaliningrad) sat on the river Pregel, which split around two islands. Seven bridges tied the two river banks and the two islands together. Try the walk yourself below. Tap a land mass to start, then tap a bridge (or the land on its far side) to cross it. A bridge can only be crossed once.
If you tried the first map, you will have got stuck. That is not a lack of cleverness. In Königsberg the walk cannot be done, and the number in each circle tells you why.
The number inside each circle is how many bridges touch that spot. Euler's insight was that nothing else about the map matters: not the shapes of the islands, not the lengths of the bridges, only which places are joined to which. Strip the map down to dots (places) and lines (bridges) and you have what mathematicians now call a graph, and the number at each dot is its degree.
Now think about what happens in the middle of a walk. You arrive at a place over one bridge and leave over another. Every pass-through uses bridges in pairs: one in, one out. So any place you merely pass through needs an even number of bridges. If it had an odd number, you would eventually arrive and find every bridge used up, stuck there.
There are exactly two places where the pairing can break: where you start (one bridge out with no matching arrival) and where you finish (one arrival with no matching departure). So a walk that uses every bridge once can exist only if the map has either no odd places, or exactly two. With none, you can start anywhere and end where you started. With two, you must start at one of them and end at the other.
Königsberg has four odd places: the large island touches five bridges and each of the other three places touches three. Four is more than the two ends a walk can supply, so no route can exist, however long you search.
Switch to Build / remove bridges on the Königsberg map. Tap a bridge to remove it, or tap a dotted ghost to build one. Watch the counts change colour: orange for odd, green for even. Remove the bridge between the two islands and the large island drops to four, one island to two, leaving exactly two odd places, so a walk now exists. Building the dotted bridge between the two banks works as well. Each change flips two counts at once, which is why the number of odd places is always even. Can one change make all four even? It cannot: each change flips only two counts, and four are odd.
The second map, the envelope drawn without lifting your pen, has exactly two odd corners, so you must start at one bottom corner. The third has five points all joined to each other, so every place has four bridges and any start works.
Euler presented his solution in 1735 to the St Petersburg Academy, where he worked, and the paper was published in 1741. He called the problem part of the "geometry of position", a kind of geometry that cares about connection rather than distance. It is usually treated as the first result in graph theory, the mathematics behind maps, networks, circuits and route-planning. He showed that more than two odd places makes the walk impossible; the full proof that two or none is also enough came later, from Carl Hierholzer in 1873.
Königsberg itself did not stay put. Bombing in the Second World War and later rebuilding left only three of the original seven bridges standing, and the city's new layout does allow such a walk. The puzzle outlived the bridges.
The lesson travels well. When a problem seems to need a huge search, ask what is conserved, here the pairing of arrivals and departures, and a single count can settle what thousands of trials could not.