Skip to main content

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


Comments

Popular posts from this blog

Fermat's Last Theorem

You may be familiar with Pythagoras’ Theorem. This simple yet significant theorem is a staple in secondary education around the world and oftentimes your best friend when it comes to geometry problems. This simple theorem is backed up with many simple and elegant proofs easily understandable by anyone who can understand the theorem itself. This is exemplified by this rearrangement proof: See how the the yellow areas in the first diagram can be rearranged to form the second diagram and how this proves Pythagoras’ Theorem. Now, there are some integers that satisfy Pythagoras’ Theorem. These are referred to as Pythagorean Triples and there is an infinite amount of them (Why?). Some small examples include (3,4,5), (5,12,13) and (8,15,17).   Finding Pythagorean Triples is an example of solving a Diophantine equation – equations which have positive integer solutions for all variables. Unsurprisingly, Diophantine equations are named after Diophantus who developed methods for solving such equa

Pythagoreanism

Pythagoras of Samos is most famously credited for discovering the theorem relating the three sides of a right angled triangle (though evidence suggests that this theorem was not discovered by Pythagoras and was actually in use in many parts of the world before Pythagoras’s birth). However, few know about the Pythagorean Brotherhood - a cult formed by Pythagoras in Croton in Southern Italy in the 5 th Century BC that lasted almost 200 years after his death. Though the Pythagoreans shared many ritualistic features with other cults such as wearing robes, observing sexual purity, maintaining utmost secrecy and loyalty, and not touching beans, it was unique in its worship of numbers and their metaphysical. Pythagoreans believed in the metaphysics of number and that reality was mathematical in nature. They also believed that spiritual purity could be achieved through the study of philosophy and mathematics. ALL IS NUMBER - Pythagorean Motto Pythagoreans believed in the concept of tetraktys,