from the world's big

thinkers

# 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:

*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.

## The “new normal” paradox: What COVID-19 has revealed about higher education

Higher education faces challenges that are unlike any other industry. What path will ASU, and universities like ASU, take in a post-COVID world?

*Photo: Luis Robayo/AFP via Getty Images*

- Everywhere you turn, the idea that coronavirus has brought on a "new normal" is present and true. But for higher education, COVID-19 exposes a long list of pernicious old problems more than it presents
*new*problems. - It was widely known, yet ignored, that digital instruction must be embraced. When combined with traditional, in-person teaching, it can enhance student learning outcomes at scale.
- COVID-19 has forced institutions to understand that far too many higher education outcomes are determined by a student's family income, and in the context of COVID-19 this means that lower-income students, first-generation students and students of color will be disproportionately afflicted.

### What conditions of the new normal were already appreciated widely?

<p>First, we understand that higher education is unique among industries. Some industries are governed by markets. Others are run by governments. Most operate under the influence of both markets and governments. And then there's higher education. Higher education as an "industry" involves public, private, and for-profit universities operating at small, medium, large, and now massive scales. Some higher education industry actors are intense specialists; others are adept generalists. Some are fantastically wealthy; others are tragically poor. Some are embedded in large cities; others are carefully situated near farms and frontiers.</p> <p>These differences demonstrate just some of the complexities that shape higher education. Still, we understand that change in the industry is underway, and we must be active in directing it. Yet because of higher education's unique (and sometimes vexing) operational and structural conditions, many of the lessons from change management and the science of industrial transformation are only applicable in limited or highly modified ways. For evidence of this, one can look at various perspectives, including those that we have offered, on such topics as <a href="https://www.insidehighered.com/digital-learning/blogs/rethinking-higher-education/lessons-disruption" target="_blank">disruption</a>, <a href="https://www.nytimes.com/2020/02/20/education/learning/education-technology.html" target="_blank">technology management</a>, and so-called "<a href="https://www.insidehighered.com/sites/default/server_files/media/Excerpt_IHESpecialReport_Growing-Role-of-Mergers-in-Higher-Ed.pdf" target="_blank">mergers and acquisitions</a>" in higher education. In each of these spaces, the "market forces" and "market rules" for higher education are different than they are in business, or even in government. This has always been the case and it is made more obvious by COVID-19.</p> <p>Second, with so much excitement about innovation in higher education, we sometimes lose sight of the fact that students are—and should remain—the core cause for innovation. Higher education's capacity to absorb new ideas is strong. But the ideas that endure are those designed to benefit students, and therefore society. This is important to remember because not all innovations are designed with students in mind. The recent history of innovation in higher education includes several cautionary tales of what can happen when institutional interests—or worse, <a href="https://www.insidehighered.com/news/2016/02/09/apollos-new-owners-seek-fresh-start-beleaguered-company" target="_blank">shareholder</a> interests—are placed above student well-being.</p>*Photo: Getty Images*

### What conditions of the new normal were emerging suspicions?

<p>Our collective thinking about the role of institutional or university-to-university collaboration and networking has benefitted from a new clarity in light of COVID-19. We now recognize more than ever that colleges and universities must work together to ensure that the American higher education system is resilient and sufficiently robust to meet the needs of students and their families.</p> <p>In recent weeks, various commentators have suggested that higher education will face a wave of institutional <a href="https://www.businessinsider.com/scott-galloway-predicts-colleges-will-close-due-to-pandemic-2020-5" target="_blank">closures</a> and consolidations and that large institutions with significant online instruction capacity will become dominant.</p> <p>While ASU is the largest public university in the United States by enrollment and among the most well-equipped in online education, we strongly oppose "let them fail" mindsets. The strength of American higher education relies on its institutional diversity, and on the ability of colleges and universities to meet the needs of their local communities and educate local students. The needs of learners are highly individualized, demanding a wide range of options to accommodate the aspirations and learning styles of every kind of student. Education will become less relevant and meaningful to students, and less responsive to local needs, if institutions of higher learning are allowed to fail. </p> <p>Preventing this outcome demands that colleges and universities work together to establish greater capacity for remote, distributed education. This will help institutions with fewer resources adapt to our new normal and continue to fulfill their mission of serving students, their families, and their communities. Many had suspected that collaboration and networking were preferable over letting vulnerable colleges fail. COVID-19's new normal seems to be confirming this.</p>*President Barack Obama delivers the commencement address during the Arizona State University graduation ceremony at Sun Devil Stadium May 13, 2009 in Tempe, Arizona. Over 65,000 people attended the graduation.*

*Photo by Joshua Lott/Getty Images*

*A graduate student protests MIT's rejection of some evacuation exemption requests. *

*Photo: Maddie Meyer/Getty Images*

### Where can the new normal take us?

<p>As colleges and universities face the difficult realities of adapting to COVID-19, they also face an opportunity to rethink their operations and designs in order to respond to social needs with greater agility, adopt technology that enables education to be delivered at scale, and collaborate with each other in order to maintain the dynamism and resilience of the American higher education system.</p> <p>COVID-19 raises questions about the relevance, the quality, and the accessibility of higher education—and these are the same challenges higher education has been grappling with for years. </p> <p>ASU has been able to rapidly adapt to the present circumstances because we have spent nearly two decades not just anticipating but <em>driving</em> innovation in higher education. We have adopted a <a href="https://www.asu.edu/about/charter-mission-and-values" target="_blank">charter</a> that formalizes our definition of success in terms of "who we include and how they succeed" rather than "<a href="https://www.washingtonpost.com/opinions/2019/10/17/forget-varsity-blues-madness-lets-talk-about-students-who-cant-afford-college/" target="_blank">who we exclude</a>." We adopted an entrepreneurial <a href="https://president.asu.edu/read/higher-logic" target="_blank">operating model</a> that moves at the speed of technological and social change. We have launched initiatives such as <a href="https://www.instride.com/how-it-works/" target="_blank">InStride</a>, a platform for delivering continuing education to learners already in the workforce. We developed our own robust technological capabilities in ASU <a href="https://edplus.asu.edu/" target="_blank">EdPlus</a>, a hub for research and development in digital learning that, even before the current crisis, allowed us to serve more than 45,000 fully online students. We have also created partnerships with other forward-thinking institutions in order to mutually strengthen our capabilities for educational accessibility and quality; this includes our role in co-founding the <a href="https://theuia.org/" target="_blank">University Innovation Alliance</a>, a consortium of 11 public research universities that share data and resources to serve students at scale. </p> <p>For ASU, and universities like ASU, the "new normal" of a post-COVID world looks surprisingly like the world we already knew was necessary. Our record breaking summer 2020 <a href="https://asunow.asu.edu/20200519-sun-devil-life-summer-enrollment-sets-asu-record" target="_blank">enrollment</a> speaks to this. What COVID demonstrates is that we were already headed in the right direction and necessitates that we continue forward with new intensity and, we hope, with more partners. In fact, rather than "new normal" we might just say, it's "go time." </p>## A temporary marriage makes more sense than marriage for life

Most marriages end in resentment. Why should longevity be the sole marker of a successful marriage?

In November 1891, the British sexologist Havelock Ellis married the writer and lesbian Edith Lees. He was 32 and a virgin. And since he was impotent, they never consummated their union. After their honeymoon, the two lived separately in what he called an open marriage. The union lasted until Lees’ death in 1916.

## Live on Tuesday | Personal finance in the COVID-19 era

Sallie Krawcheck and Bob Kulhan will be talking money, jobs, and how the pandemic will disproportionally affect women's finances.

## How DNA revealed the woolly mammoth's fate – and what it teaches us today

Scientists uncovered the secrets of what drove some of the world's last remaining woolly mammoths to extinction.

Every summer, children on the Alaskan island of St Paul cool down in Lake Hill, a crater lake in an extinct volcano – unaware of the mysteries that lie beneath.

## Conspicuous consumption is over. It’s all about intangibles now

These new status behaviours are what one expert calls 'inconspicuous consumption'.