On cars, old, new and future; science & technology; vintage airplanes, computer flight simulation of them; Sherlockiana; our English language; travel; and other stuff
“THE SEVEN Bridges of Königsberg” sounds like a romantic novel set elsewhere than Iowa. In fact, though, it’s a classic problem of mathematics, one that led to modern mathematics’ graph theory, topology and theory of networks.
Königsberg, Prussia, B and C, is on the Pregel River, with two major islands, A and D, seven bridges, a through f, being part of the landscape in the 1700s.
A Google Map of what is now Kalingrad, Russia, shows that, indeed, five of the seven crossings still exist. Two of them, a and c, are the major thoroughfare of Leninsky Prospect. The third bridge, e, is on Kahta Street connecting the larger island D to Königsberg Cathedral on A, the smaller one. Modern bridges g and f are now part of Oktyabrskaya Street. The other two historic bridges, b and d, linking the Cathedral to the city proper, were destroyed in World War II.
And aren’t Google Maps fun, especially in satellite mode?
Back in the 1700s, Königsbergers entertained themselves with a puzzle: Was it possible to take a continuous stroll of all seven bridges without crossing any bridge twice?
Leonard Euler is considered the greatest mathematical mind of the 1700s. James R. Newman cites in The World of Mathematics that “Euler calculated without apparent effort, as men breathe, or as eagles sustain themselves in the wind…. He dashed off memoirs in the half-hour between the first and second calls to dinner.”
Euler solved the Seven Bridges of Königsberg puzzle in the negative (a more difficult task than showing it could be done). In doing so, he distilled the puzzle into its essentials in a way that’s characteristic of modern mathematics: Seek generalities rather than specifics. Study relationships in the abstract.
Each node of his graph represents a land mass; each edge represents a bridge. Everything else in the Königsberg map is irrelevant, as are the relative placements of nodes and edges. This idea of deformable invariants is fundamental to the modern mathematical area of topology (think about the similarity of a doughnut and a coffee cup—each is pierced with a single hole).
The puzzle can then be restated: Can a continuous path trace each edge of the graph precisely once?
Euler reasoned that, with the exception of the start and end of a successful Königsberg walk, a land mass is entered by one bridge and left by another. Thus, he recognized that these intermediate nodes must have an even number of edges, “nodes of even degree.” Others are nodes of odd degree.
Finally, he concluded that a successful walk must have either precisely two nodes of odd degree (the start and end) or none at all. Since the four nodes of the Königsberg puzzle all have odd degree, there is no successful bridge tour.
In his honor, such a walk is also called an Eulerian path.
As a final exercise (extra credit!), sketch a map with islands and bridges that fits the geography of this particular Euler walk. ds
© Dennis Simanaitis, SimanaitisSays.com, 2014