At the beginning of the 18th century, the Prussian city of Königsberg was divided into four regions separated by branches of the River Pregel: the two banks, the island of Kneiphof, and the district of Lomse. Connecting them were seven bridges: Kneiphof had two bridges to each bank, Lomse had one to each bank, and the seventh bridge connected Kneiphof to Lomse.
We don’t know how or when the question arose: is it possible to take a tour of the four regions crossing each bridge only once? The great Leonhard Euler solved the problem in 1735 as follows:
Each time the tour passes through one of the regions, two bridges are crossed: one to enter, the other to leave. So, apart from the departure and arrival regions, all the others must be served by an even number of bridges. But in Königsberg every region had an odd number of bridges: 5 at Kneiphof and 3 at each other. Therefore, the requested tour could not exist.
A crucial aspect of Euler’s reasoning is abstraction: the details are irrelevant, all that matters are the regions, which we can represent as points, and the bridges, which we can represent as lines connecting those points. Such configurations, formed by a certain number of points connected, in pairs, by lines, are called “graphs”.
Another key aspect is generality: Euler’s theorem applies to any graph, not just the Königsberg graph: there is an Eulerian walk (that is, one that crosses each line exactly once) if and only if, taking away the points of departure and arrival, all others are served by an even number of lines.
Graph theory is one of the most productive areas of mathematics today and has numerous practical applications in areas such as electrical circuit design, network management (including internet and social networks), brain study, modeling of social phenomena, logistics transport, urban planning and many others, which move billionaire segments of the economy.
Two of the bridges were destroyed in World War II. The others are in their original locations (three are reconstructions). Therefore, currently each of the banks is served by only two bridges. Therefore, it is now possible to take Eulerian tours in Königsberg, as long as they start at Kneiphof and end at Lomse, or vice versa.
But it is no longer Königsberg: at the end of the war the city was integrated into Russia and renamed Kaliningrad. And the name of the river also changed to Pregola.
