Walk Like an Eulerian: the Bridges of Königsberg

How a riddle involving one river, two islands and seven bridges prompted a mathematician to lay the foundation for graph theory

Leonhard Euler (1707-1783) was one of the world’s most important mathematicians, and certainly is a candidate for the most prolific: in 1775 alone, he wrote an average of one mathematical paper per week. During his lifetime, he published more than 500 books and papers. His collected works would fill up to 80 quarto volumes.


Euler made important contributions to fields as diverse as optics, graph theory, fluid dynamics and astronomy. The list of functions, theorems, equations and numbers named after Euler is so long that some joke that they really should be named after the first person after Euler to discover them (1).

An apocryphal tale has Euler, a devout Christian, silencing the free-thinking French philosopher Diderot with a mathematical formula proving the existence of God (2). But perhaps Euler’s best-remembered contribution to science is his solution to the so-called Problem of the Seven Bridges of Königsberg. Maybe because it involves an easily graspable map, rather than abstruse algebraic formulae.

The Prussian city of Königsberg (3) spanned both banks of the river Pregel, which washes around the Kneiphof, a small island at the centre of town, and a larger island immediately to its east. Seven bridges connected both banks and both islands with each other. A popular pastime among the citizens of Königsberg was to attempt a solution to a seemingly intractable problem: How to walk across both banks and both islands by crossing each of the seven bridges only once. The names of the bridges, west to east and north to south, are:

  • Krämerbrücke (Traders’ Bridge)
  • Schmiedebrücke (Forged Bridge)
  • Holzbrücke (Wood Bridge)
  • Grüne Brücke (Green Bridge)
  • Köttelbrücke (Dung Bridge)
  • Dombrücke (Cathedral Bridge)
  • Hohe Brücke (High Bridge)
  • Hohe Brücke to the south of the Fähre (ferry), outside of this map. For complete map of Königsberg in 1905, see here.

    In 1735, Euler reformulated the riddle in abstract terms - and once and for all proved that the Königsberg Bridge Problem was indeed unsolvable. Euler recast the actual location as an set of nodes (vertices) connected by links (edges). The exact layout of the terrain did not matter, as long as the nodes remained linked in the original way. He then solved the problem analytically rather than by exhaustively listing all possible permutations:

    “My whole method relies on the particularly convenient way in which the crossing of a bridge can be represented. For this I use the capital letters A, B C, D, for each of the land areas separated by the river. If a traveler goes from A to B over bridge a or b, I write this as AB, where the first letter refers to the area the traveler is leaving, and the second refers to the area he arrives at after crossing the bridge. Thus, if the traveler leaves B and crosses into D over bridge f, this crossing is represented by BD, and the two crossings AB and BD combined I shall denote by the three letters ABD, where the middle letter B refers to both the area which is entered in the first crossing and to the one which is left in the second crossing.”

    Map from Euler's paper on the problem. Note the bridge names do not match those on the above map.

    Euler proved that the Bridges Problem could only be solved if the entire graph has either zero or two nodes with odd-numbered connections, and if the path (4) starts at one of these odd-numbered connections, and ends at another one. Königsberg has four nodes of odd degree, and thus cannot have an Eulerian Path.

    Euler’s analytical solution to the Königsberg Problem is seen as the first theorem of graph theory, an important stage in the development of topography, and a founding text of network science.

    Sadly, the original topography for this Problem is all but gone. Those attempting a mathematical pilgrimage to Kaliningrad’s Seven Bridges will be sorely disappointed. Two bridges were destroyed by bombing at the end of the Second World War, two more were demolished and replaced by a Soviet highway. Of the other three originals, one other had been rebuilt in 1935. So of the remaining five, only two date from Euler’s time. 

    Does the newer, Soviet configuration make it possible to cross all bridges only once? Darn it, we should have paid more attention in math class. For a more extensive treatment of Euler's paper, including the conclusion that should be able to solve the newer riddle as well, see this document at the Mathematical Association of America.

    Google Maps showing the Knaypkhof today, including the grave of Immanuel Kant. 

    Unless mentioned otherwise, the images for this post were taken from Visual Complexity: Mapping Patterns of Information, by Manuel Lima. The book discusses and demonstrates the visualisation of networks, largely a modern field, again with Euler as one of its earliest pioneers.

    Strange Maps #536

    Got a strange map? Let me know at strangemaps@gmail.com.

    (1) An impressively long list here. Not included are Euler’s so-called carrés magiques, 81-square grid puzzles that some consider to be early versions of sudoku. 

    (2) Pour la petite histoire: (a+b^n)/n=x - although Euler mainly proved that Diderot didn’t know enough about algebra to reply in kind.

    (3) Presently the Russian city of Kaliningrad, enclaved between Poland and Lithuania.

    (4) Such routes are called Euler Walks or Eulerian Paths in the mathematician’s honour.

    ​There are two kinds of failure – but only one is honorable

    Malcolm Gladwell teaches "Get over yourself and get to work" for Big Think Edge.

    Big Think Edge
    • Learn to recognize failure and know the big difference between panicking and choking.
    • At Big Think Edge, Malcolm Gladwell teaches how to check your inner critic and get clear on what failure is.
    • Subscribe to Big Think Edge before we launch on March 30 to get 20% off monthly and annual memberships.
    Keep reading Show less

    Why are so many objects in space shaped like discs?

    It's one of the most consistent patterns in the unviverse. What causes it?

    Videos
    • Spinning discs are everywhere – just look at our solar system, the rings of Saturn, and all the spiral galaxies in the universe.
    • Spinning discs are the result of two things: The force of gravity and a phenomenon in physics called the conservation of angular momentum.
    • Gravity brings matter together; the closer the matter gets, the more it accelerates – much like an ice skater who spins faster and faster the closer their arms get to their body. Then, this spinning cloud collapses due to up and down and diagonal collisions that cancel each other out until the only motion they have in common is the spin – and voila: A flat disc.

    Scientists study tattooed corpses, find pigment in lymph nodes

    It turns out, that tattoo ink can travel throughout your body and settle in lymph nodes.

    17th August 1973: An American tattoo artist working on a client's shoulder. (Photo by F. Roy Kemp/BIPs/Getty Images)
    popular

    In the slightly macabre experiment to find out where tattoo ink travels to in the body, French and German researchers recently used synchrotron X-ray fluorescence in four "inked" human cadavers — as well as one without. The results of their 2017 study? Some of the tattoo ink apparently settled in lymph nodes.


    Image from the study.

    As the authors explain in the study — they hail from Ludwig Maximilian University of Munich, the European Synchrotron Radiation Facility, and the German Federal Institute for Risk Assessment — it would have been unethical to test this on live animals since those creatures would not be able to give permission to be tattooed.

    Because of the prevalence of tattoos these days, the researchers wanted to find out if the ink could be harmful in some way.

    "The increasing prevalence of tattoos provoked safety concerns with respect to particle distribution and effects inside the human body," they write.

    It works like this: Since lymph nodes filter lymph, which is the fluid that carries white blood cells throughout the body in an effort to fight infections that are encountered, that is where some of the ink particles collect.

    Image by authors of the study.

    Titanium dioxide appears to be the thing that travels. It's a white tattoo ink pigment that's mixed with other colors all the time to control shades.

    The study's authors will keep working on this in the meantime.

    “In future experiments we will also look into the pigment and heavy metal burden of other, more distant internal organs and tissues in order to track any possible bio-distribution of tattoo ink ingredients throughout the body. The outcome of these investigations not only will be helpful in the assessment of the health risks associated with tattooing but also in the judgment of other exposures such as, e.g., the entrance of TiO2 nanoparticles present in cosmetics at the site of damaged skin."

    Photo by Alina Grubnyak on Unsplash
    Mind & Brain

    Do human beings have a magnetic sense? Biologists know other animals do. They think it helps creatures including bees, turtles and birds navigate through the world.

    Keep reading Show less