### The 7 Bridges of Königsberg

Königsberg was a Prussian city (presently Kalingrad, Russia) in the 18th century. The city had seven bridges connecting four landmasses as shown in the diagram.

According to folklore, the following question was a popular mathematical puzzle at the time:

Could one take a walk through the city in such a way that each bridge would be crossed once?

Though many had attempted the problem, they could not prove that their answer was indeed correct. Enter Euler. Euler tackled this problem in 1735, proving exactly why his answer was correct and subsequently creating the field of graph theory.

Leonhard Euler (1707-1783) was an extremely prolific mathematician. Most people will know of his constant e, from high school mathematics as well as his multitude of other accomplishments. Euler had such a huge mathematical influence that Pierre-Simon Laplace quoted "Lisez Euler, lisez Euler, c'est notre maître à tous." Which some of you French learners/speakers will know roughly translates to “Read Euler, read Euler, he is the master of us all”.

Euler represented the city and its bridges as a series of vertices and edges as shown in the diagram below. Each landmass is represented by a vertex and each bridge by an edge.

Each vertex has a degree which is the number of edges that enter or exit from it. A path that travels along each edge exactly once is called an Euler Walk. A path which travels along each edge exactly once and ends up on the same vertex as it started on is called an Euler Circuit. The Königsberg bridge problem can be restated to whether or not an Euler Walk on the graph is possible.

The answer is no. For an Euler Walk to exist, there must exist at most two vertices of odd degree. This is because for the middle vertices, there must be a path to enter and to exit. The one or two vertices with an odd degree are the start and end points of the path. Examining the Königsberg bridge graph, we can see that this is not the case and therefore, an Euler Walk is not possible. So it is not possible for one to take a walk through the city in such a way that each bridge would be crossed once.

For an Euler Circuit to exist, each vertex must have an even degree. Again, this is because there must be a path to enter and to exit each vertex.

Now you too can wield the power of Euler’s graph theory the next time someone presents you with a little puzzle like this one:

Can you draw this shape without lifting your pen up from the page?

Sources:
Image of the Bridges of Königsberg; John Easton