The bridges of the ancient city of Königsberg posed a famous and almost problematic challenge a few centuries ago. But this isn’t just about the math problem; it’s also a story about a famous Swiss mathematician named Leonhard Euler who founded the study of topology and graph theory by solving this problem. The effects of this problem have lasted centuries, and have helped develop several parts of our understanding of mathematics.
We don’t hear too much about Euler, but he is one of the most important and influential mathematicians ever, along with Archimedes and Newton. He created more published works than any other mathematician and wrote in a very understandable way. There is a fundamental part of geometry that all other mathematicians before him missed, but Euler discovered it and made the polyhedron formula: V-E+F=2
Euler stayed in Königsberg during the year 1736 while in the area of St. Petersburg. Here, he began developing a new idea called geometriam situs, later called topology. Different from topography, topology is the study of non-rigid shapes. It is about the properties of geometric figures on a surface that are unaltered when the surface is deformed.
The city of Königsberg was located in Russia on the river Pregel. Being founded in the thirteenth century by the Teutonic Knights, it was a major commercial and industrial city. During World War II it was captured and heavily ruined by communists, then had its name changed to Kaliningrad, which is its name today. Konigsberg was built around a river that created four land masses, including an island in the middle called Kneiphof Island. Euler came across this famous question during his stay in the city: “Is it possible for a pedestrian to walk across all seven bridges in Königsberg without crossing any bridge twice?” The problem cannot be solved by simply hearing the question, which is unusual for mathematical problems, but you must view a map of the city or a graph of the layout of the bridges.
At first Euler dismissed the problem and said it was only solvable by reason, but later began to consider it. He realized that it didn’t fit into any current form of mathematics because relative size and position of the bridges didn’t matter. He had the idea of a graph showing all the bridge locations by making every land mass, or part of the city you could visit, represented as points, or vertices. Every bridge you could cross was a line, or edge, that connected the vertices. Euler actually never drew a graph to represent the problem; that did not happen until much later, but he did explain it in his works.
If you were to follow the edges all over the graph and not double back once, you have completed an Euler walk. If you end up at the same vertex you began, it would be an Euler circuit. A vertex’s degree is how many edges that connect to it, and a loop around to the same vertex counts as a degree of two. So, a vertex that has four edges, or paths, connected to it simply has a degree of...