Seven bridges, one impossible walk.
Could you walk through Königsberg, cross every bridge exactly once, and end up where you started? The Explorer lets you try the walk yourself, watch the parity argument live as you cross each bridge, and add or remove bridges to make the walk possible.
Königsberg straddled the Pregel river with two islands and two riverbanks — four land masses in total — connected by seven bridges. The townspeople asked a Sunday-stroll question: could you take a walk through the city that crossed every bridge exactly once and ended where you started? Everyone tried. Everyone failed. Nobody could prove it was impossible.
In 1736 Leonhard Euler did something nobody had done before. He ignored distances. He ignored angles. He ignored which bridge was upstream of which. He drew the four land masses as four dots and the seven bridges as seven edges. The map became a graph. The problem of position — geometria situs — was born, and with it both graph theory and topology.
Every time you enter a land mass, you use one bridge; when you leave, you use another. So each land mass needs an even number of bridges incident to it — except, possibly, the start and the end of the walk. Königsberg had four land masses, all with an odd number of bridges. Four odd-degree vertices is two too many. Impossible.
The same parity argument now powers GPS routing, the Chinese Postman Problem (used to optimise routes for snowploughs, garbage trucks and postal workers), and DNA assembly — every modern genome assembler walks an Eulerian path through a de Bruijn graph. WWII destroyed two of Königsberg's bridges; only five of the original seven remain. The current graph has exactly two odd-degree vertices, so today the walk is finally possible — though Euler is no longer there to take it.
How and where this technique lives in the world today.
Topics in the same vein.
