Wedged between Poland and Lithuania, along the Baltic Coast, is a piece of Russia located 200 miles away from the Russian border. The Kaliningrad oblast, an exclave of Russia, was originally a Prussian state before it was transferred over to the Soviet Union after the end of the Second World War when the Allied powers met at Potsdam to decide who gets which territory. Back then Kaliningrad was known as Königsberg. If that name doesn’t ring any bells then you are definitely not a mathematician.
Königsberg’s association with science and mathematics goes back to the 18th century. The city was then a hub for science and cultural wizardry from Germany, Poland and Lithuania. Königsberg was the birthplace of the famous mathematicians Christian Goldbach—whom we today remember for the Goldbach's conjecture which is one of the oldest and best-known unsolved problems in number theory, David Hilbert—the formulator of Hilbert spaces, and Carl Neumann—for the famous Neumann series we learned in high school.
A bird's-eye view of Königsberg, as in late 16th century.
Königsberg was also the home of renowned physicist Gustav Kirchhoff (Kirchhoff's laws are fundamental in the design of any electrical and electronic circuits) and Nobel Prize winner chemist Otto Wallach. The famed philosopher Immanuel Kant, another Königsberg-born, was so proud of his home town that he barely left the place in his entire lifetime.
While all these gifted sons of Königsberg made the city proud, it was Swiss mathematician Leonard Euler who actually immortalized the name of Königsberg.
Konigsberg, or Kaliningrad now, is situated on the Pregel River. As the river flows through the city, it branches out creating two large islands—Kneiphof and Lomse. Back in the 18th century, these islands were connected to the river’s north and south banks as well as to each other by seven bridges that were central to the city’s life. While crossing and re-crossing these bridges countless number of times during their Sunday afternoon walks, the citizens of Königsberg set upon themselves a puzzle: Was it possible to devise a route through the city that involves crossing all the seven bridges once and only once? Nobody could work out an answer until Leonard Euler in St. Petersburg heard about the problem.
Map of Königsberg with the seven bridges labeled, circa 1905.
At first Euler was annoyed that the mayor of Danzig wrote to him asking for his help, when he clearly was such a busy man. In a 1736 letter to Carl Leonhard Gottlieb Ehler, the mayor of Danzig, Euler expressed his displeasure:
. . . Thus you see, most noble Sir, how this type of solution bears little relationship to mathematics, and I do not understand why you expect a mathematician to produce it, rather than anyone else, for the solution is based on reason alone, and its discovery does not depend on any mathematical principle. Because of this, I do not know why even questions which bear so little relationship to mathematics are solved more quickly by mathematicians than by others.
Even though Euler found the problem trivial, he was still intrigued by it. Later, the same year, Euler wrote to Giovanni Marinoni, an Italian mathematician and engineer:
This question is so banal, but seemed to me worthy of attention in that geometry, nor algebra, nor even the art of counting was sufficient to solve it. In view of this, it occurred to me to wonder whether it belonged to the geometry of position which Leibniz had once so much longed for. And so, after some deliberation, I obtained a simple, yet completely established, rule with whose help one can immediately decide for all examples of this kind, with any number of bridges in any arrangement, whether such a round trip is possible, or not....
Very soon, Euler had worked out a solution. The answer wasn’t terribly exciting—no, you cannot cross all the bridges only once and return to your starting point. But in working out a solution what Euler did was invent a new technique of analysis and eventually a new branch of mathematics now known as graph theory.
Euler realized that in the Königsberg problem, the exact lay-out of the city or the choice of route taken is irrelevant. The only thing that is important is how things are connected. This allowed him to turn the complicated map of the city into a neat network, also called graph, with dots representing land masses and links between them as bridges.
Euler observed that if every link (i.e. a bridge) is to be crossed over only once, then each node (i.e. a land mass) must have an even number of links attached to it. That’s because whenever you enter one by a link, you need to leave it by another. So the node needs two links if you visit it once, four if you visit it twice and so on. The only nodes that can have an odd number of links attached to them are the nodes where the walk starts and ends.
Now, by looking at the graph we can tell why the answer to the Königsberg problem is negative—every node on the graph has an odd number of links attached to them. In essence, Euler showed that the possibility of a walk through a graph, traversing each link exactly once, depends on the number of links the nodes are connected to. The beauty of this argument is that it works for any network, no matter how large or complex.
Today, graph theory is a major tool in mathematical research, and finds application in diverse fields such as electrical engineering, computer programming and networking, business administration, sociology, economics, marketing, and communications—the list goes on and on. Recent research suggests that graph theory can provide fascinating insights into the breakdown of communication between nerve cells that results in the progressive memory loss of Alzheimer's.
The Old cathedral of Kaliningrad in Kneiphof island. Photo credit: Gumerov Ildar/Wikimedia
Crossing the seven bridges of Königsberg, as Euler proved with mathematical rigor, is as impossible today as was in Euler’s time, not because of lack of an efficient route but because most of the bridges no longer exist in their original form. Two of the bridges—Krämerbrückenfest, or the Merchant’s Bridge, and Green Bridge—leading to and from Kneiphof island were destroyed during the Second World War and were replaced by a 500-meter long concrete flyover.
Two other bridges—Schmiedebrücke, or the Forge bridge, and Köttelbrücke—also didn’t survive the extensive bombing during the Second World War, and were not replaced.
Honigbrücke or the Honey Bridge connects the island of Lomse to eastern Kneiphof. This bridge is the only Kneiphof bridge that survived the Second World War and can still be seen today.
Holzbrücke or the Wooden Bridge connecting Lomse to the northern bank of Pregel River also survived the Second World War and still exists today.
The seventh and the final bridge, Hohe Brücke, or the High Bridge, once lead to Lomse. It was demolished and replaced by a new bridge.
An undated picture of the Green Bridge before it was destroyed.
The Merchant Bridge.
Both the Green Bridge and Merchant Bridge was replaced by this modern overpass. Photo credit: Padonak39/Wikimedia
Schmiedebrücke, or the Forge bridge.
Köttelbrücke.
The Honey Bridge.
Holzbrücke or the Wooden Bridge.
The High Bridge.
