The Seven Bridges of Königsberg

Introduction

Our destination is 1735 and the Prussian city of Königsberg. This city, which today is Kaliningrad, Russia, comprised both banks of the Pregel River as well as two river islands; seven bridges connected these four different parts of the city, as illustrated in the figure below (top). Königsberg’s residents enjoyed taking walks, and they asked a simple question: Is it possible to set out from my house, cross each bridge exactly once, and return home? Their question became known as the Bridges of Königsberg Problem.

Exercise Break: Does the Bridges of Königsberg Problem have a solution?

In 1735, Leonhard Euler drew the graph in the figure below (bottom), which we call Königsberg; this graph’s nodes represent the four sectors of the city, and its edges represent the seven bridges connecting different sectors. Note that the edges of Königsberg are undirected, meaning that they can be traversed in either direction.

STOP and Think: Redefine the Bridges of Königsberg Problem as a question about the graph Königsberg.