A Walk Through Konigsberg That Couldn't Be Done Started a Whole Branch of Math

Eighteenth-century Königsberg, the Prussian university town that is now Russian Kaliningrad, sat astride the Pregel River. The river forked around two islands in the middle of the city, and seven bridges connected the islands and the two opposite banks. The puzzle the locals discussed in coffeehouses was whether you could walk a route through the city that crossed each bridge exactly once and brought you back to your starting point.

Nobody could do it. Nobody could prove it was impossible either, until the Swiss mathematician Leonhard Euler — then about 28 and working at the St Petersburg Academy of Sciences — heard the question and recognised it as something deeper than recreational geometry. He presented his solution to the academy on 26 August 1735, and published it in 1741 under the title Solutio problematis ad geometriam situs pertinentis — the solution to a problem in the geometry of position.

Euler's move was to throw away everything that did not matter. He said: forget the lengths of the bridges, the shapes of the islands, the actual map. What matters is which land masses are connected to which, and by how many bridges. Each piece of land becomes a dot. Each bridge becomes a line between two dots. The question becomes: starting from any dot, can you trace every line exactly once? Euler proved that you can do it only if the graph has either zero or exactly two dots with an odd number of lines coming out of them. Königsberg had four. The walk was impossible.

This was the first proof in what we now call graph theory — an entire branch of mathematics that today underwrites Google search, traffic routing, neural networks, and the layout of computer chips. Two of Königsberg's seven bridges were destroyed in the Second World War; the city has since been rebuilt with five. The walk is still impossible.