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

Walk Like an Eulerian: the Bridges of Königsberg

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.

    A landslide is imminent and so is its tsunami

    An open letter predicts that a massive wall of rock is about to plunge into Barry Arm Fjord in Alaska.

    Image source: Christian Zimmerman/USGS/Big Think
    Surprising Science
    • A remote area visited by tourists and cruises, and home to fishing villages, is about to be visited by a devastating tsunami.
    • A wall of rock exposed by a receding glacier is about crash into the waters below.
    • Glaciers hold such areas together — and when they're gone, bad stuff can be left behind.

    The Barry Glacier gives its name to Alaska's Barry Arm Fjord, and a new open letter forecasts trouble ahead.

    Thanks to global warming, the glacier has been retreating, so far removing two-thirds of its support for a steep mile-long slope, or scarp, containing perhaps 500 million cubic meters of material. (Think the Hoover Dam times several hundred.) The slope has been moving slowly since 1957, but scientists say it's become an avalanche waiting to happen, maybe within the next year, and likely within 20. When it does come crashing down into the fjord, it could set in motion a frightening tsunami overwhelming the fjord's normally peaceful waters .

    "It could happen anytime, but the risk just goes way up as this glacier recedes," says hydrologist Anna Liljedahl of Woods Hole, one of the signatories to the letter.

    The Barry Arm Fjord

    Camping on the fjord's Black Sand Beach

    Image source: Matt Zimmerman

    The Barry Arm Fjord is a stretch of water between the Harriman Fjord and the Port Wills Fjord, located at the northwest corner of the well-known Prince William Sound. It's a beautiful area, home to a few hundred people supporting the local fishing industry, and it's also a popular destination for tourists — its Black Sand Beach is one of Alaska's most scenic — and cruise ships.

    Not Alaska’s first watery rodeo, but likely the biggest

    Image source: whrc.org

    There have been at least two similar events in the state's recent history, though not on such a massive scale. On July 9, 1958, an earthquake nearby caused 40 million cubic yards of rock to suddenly slide 2,000 feet down into Lituya Bay, producing a tsunami whose peak waves reportedly reached 1,720 feet in height. By the time the wall of water reached the mouth of the bay, it was still 75 feet high. At Taan Fjord in 2015, a landslide caused a tsunami that crested at 600 feet. Both of these events thankfully occurred in sparsely populated areas, so few fatalities occurred.

    The Barry Arm event will be larger than either of these by far.

    "This is an enormous slope — the mass that could fail weighs over a billion tonnes," said geologist Dave Petley, speaking to Earther. "The internal structure of that rock mass, which will determine whether it collapses, is very complex. At the moment we don't know enough about it to be able to forecast its future behavior."

    Outside of Alaska, on the west coast of Greenland, a landslide-produced tsunami towered 300 feet high, obliterating a fishing village in its path.

    What the letter predicts for Barry Arm Fjord

    Moving slowly at first...

    Image source: whrc.org

    "The effects would be especially severe near where the landslide enters the water at the head of Barry Arm. Additionally, areas of shallow water, or low-lying land near the shore, would be in danger even further from the source. A minor failure may not produce significant impacts beyond the inner parts of the fiord, while a complete failure could be destructive throughout Barry Arm, Harriman Fiord, and parts of Port Wells. Our initial results show complex impacts further from the landslide than Barry Arm, with over 30 foot waves in some distant bays, including Whittier."

    The discovery of the impeding landslide began with an observation by the sister of geologist Hig Higman of Ground Truth, an organization in Seldovia, Alaska. Artist Valisa Higman was vacationing in the area and sent her brother some photos of worrying fractures she noticed in the slope, taken while she was on a boat cruising the fjord.

    Higman confirmed his sister's hunch via available satellite imagery and, digging deeper, found that between 2009 and 2015 the slope had moved 600 feet downhill, leaving a prominent scar.

    Ohio State's Chunli Dai unearthed a connection between the movement and the receding of the Barry Glacier. Comparison of the Barry Arm slope with other similar areas, combined with computer modeling of the possible resulting tsunamis, led to the publication of the group's letter.

    While the full group of signatories from 14 organizations and institutions has only been working on the situation for a month, the implications were immediately clear. The signers include experts from Ohio State University, the University of Southern California, and the Anchorage and Fairbanks campuses of the University of Alaska.

    Once informed of the open letter's contents, the Alaska's Department of Natural Resources immediately released a warning that "an increasingly likely landslide could generate a wave with devastating effects on fishermen and recreationalists."

    How do you prepare for something like this?

    Image source: whrc.org

    The obvious question is what can be done to prepare for the landslide and tsunami? For one thing, there's more to understand about the upcoming event, and the researchers lay out their plan in the letter:

    "To inform and refine hazard mitigation efforts, we would like to pursue several lines of investigation: Detect changes in the slope that might forewarn of a landslide, better understand what could trigger a landslide, and refine tsunami model projections. By mapping the landslide and nearby terrain, both above and below sea level, we can more accurately determine the basic physical dimensions of the landslide. This can be paired with GPS and seismic measurements made over time to see how the slope responds to changes in the glacier and to events like rainstorms and earthquakes. Field and satellite data can support near-real time hazard monitoring, while computer models of landslide and tsunami scenarios can help identify specific places that are most at risk."

    In the letter, the authors reached out to those living in and visiting the area, asking, "What specific questions are most important to you?" and "What could be done to reduce the danger to people who want to visit or work in Barry Arm?" They also invited locals to let them know about any changes, including even small rock-falls and landslides.

    Harvard study finds perfect blend of fruits and vegetables to lower risk of death

    Eating veggies is good for you. Now we can stop debating how much we should eat.

    Credit: Pixabay
    Surprising Science
    • A massive new study confirms that five servings of fruit and veggies a day can lower the risk of death.
    • The maximum benefit is found at two servings of fruit and three of veggies—anything more offers no extra benefit according to the researchers.
    • Not all fruits and veggies are equal. Leafy greens are better for you than starchy corn and potatoes.
    Keep reading Show less

    Cephalopod aces 'marshmallow test' designed for eager children

    The famous cognition test was reworked for cuttlefish. They did better than expected.

    The common cuttlefish

    Credit: Hans Hillewaert via Wikicommons
    Surprising Science
    • Scientists recently ran the Stanford marshmallow experiment on cuttlefish and found they were pretty good at it.
    • The test subjects could wait up to two minutes for a better tasting treat.
    • The study suggests cuttlefish are smarter than you think but isn't the final word on how bright they are.
    Keep reading Show less
    13-8

    If we do find alien life, what kind will it be?

    Three lines of evidence point to the idea of complex, multicellular alien life being a wild goose chase. But are we clever enough to know?

    Quantcast