The Prussian city of Königsberg (now Kaliningrad in Russia) was crossed by the Pregel River and connected by seven bridges which joined together two islands and the opposite shores, dividing the city into four areas. Legend has it that a curious pastime circulated among the inhabitants: finding a path that crossed all the bridges only once. A simple idea, but no one seemed to succeed.
The matter ended up in the hands of the mathematician Leonhard Euler (in Italian known as Euler). At the beginning Euler was not convinced that it was a real mathematical problem, but observing the map of the city he had a decisive intuition: it did not matter how one moved through the four areas of the city (in the figure A, B, C and D), but only the order where bridges were crossed.
Hence the brilliant simplification: represent the portions of land as points and bridges like lines.
And so the problem could be summarized like this:
Without realizing it, Euler was inventing the basis of a new discipline, graph theory, which is still fundamental today for studying patterns that can be reduced to elements and connections.
A graph is a simple way to represent links: it consists of points (called nodes) e lines that join those points (called arcs).
Analyzing the system, he discovered that the possibility of crossing all the bridges only once depends exclusively on the number of lines that “touch” each point, that is, on the degree of nodes. Such a path – today called Eulerian path – it is only possible if:
- all nodes have an even degree (i.e. an even number of lines connected to the point),
or
- exactly two nodes have odd degrees (starting and ending points).
The problem? In Königsberg all four nodes were of odd degree. In other words, the city challenge was impossible from the start.
Ironically, the only way to make the puzzle solvable would have been to eliminate at least one of the bridges. Which really happened, but in a tragic way: during the Second World Warpart of the city and some bridges were destroyed by bombing, before Königsberg was transformed into what it is today Kaliningrad.
Euler’s solution, however, has survived much longer than the original bridges. That simple urban puzzle gave rise to graph theory and, more generally, to a new way of thinking about shapes and connections, paving the way for modern topology.
