Königsberg's seven bridges problem is one of the most well-known problems in the history of mathematics. Interestingly, it was just a simple question asked by the Danzig city mayor Carl Ehler. The goal was to cross all seven bridges of Königsberg with the condition that one has to cross a bridge only once. Let us see the structure and layout of the bridges. The city of Königsberg in Prussia was divided into two mainlands by the Pregel river. The river had two islands. A total of seven bridges connected the mainland and islands, as shown in the below picture.
What is the route by which one can cross all seven bridges without crossing any of them more than once? Carl Ehler was also a mathematician. He thought about a solution to the problem. But, he couldn't find any route which met the above condition. He wrote a letter to Leonhard Euler asking him the solution to the problem. Euler stated in a response that the problem has a little relationship with Mathematics. He did not understand why Ehler expected a mathematician to solve the problem. Although Euler felt the problem trivial at first, he found its connection with the work by Leibniz. Euler realized that this problem had no direct connection with Algebra, Geometry, or any other mathematical stream that existed then but had to do something with Leibniz's idea of the geometry of positions. Later, Euler presented a paper in the year 1735 on the solution to the problem. This paper became a foundational work for a branch of Mathematics, now referred to as Graph theory.
Euler proved that there is no route by which one can cross all seven bridges of Königsberg without crossing any of them more than once. Furthermore, he also mentioned why this is not possible. Let us transform the bridge layout of the map into a pictorial representation to understand Euler's explanation.
K1 and K2 represent two mainlands of Königsberg. I1 and I2 represent two islands in the Pregel river. K1, K2, I1, and I2 in green circles are called vertices (nodes). The black curved lines representing the seven bridges are called edges. The complete pictorial representation with vertices and edges is called a graph.
Euler defined a property named as a degree for each vertice of the graph. The degree is the number of edges to which a vertex is connected. In Königsberg's bridges problem, vertex I1 is connected to the five edges (bridges). So, vertex I1 has degree five. The following diagram shows the degree for each vertex for the given problem.
Euler pointed out that the vertices should have an even degree to traverse each edge only once except the start and endpoint vertex. Let us quickly understand this by the following example of a small graph having three vertices and two edges.
Except for the start and end vertex, the remaining vertex has an even degree two. The even degree of a vertex is necessary to enter from the start and leave to the end vertex. No vertex of the graph of Königsberg's bridges has even degree. Hence, it is not possible to cross all bridges without crossing any of them.
The path to traverse all edges without repeating any edge more than once is called the Eulerian path. A graph having an Eulerian path has at most two vertices of odd degree. This is the first theorem in Graph theory.
What should be modified in the layout of Königsberg's seven bridges problem to cross all of them without crossing any of them more than once? In short, how can we achieve the Eulerian path in Königsberg's seven bridges problem? The answer is to remove any of a bridge. Let us remove the bridge connecting mainland K1 and island I2. The graph now looks the same as follows.
After the modification, we have got at the most two vertices having odd degrees (I1 and K2). And all other vertices have even degrees. Thus, the graph has the Eulerian path. The possible Eulerian path is a-b-c-d-e-f.
If a graph has,
the Eulerian path,
has two vertices with odd degrees,
Then, the Eulerian path will start at one of the odd degree vertices and end at the other.
Observe the starting and ending points of the Eulerian path a-b-c-d-e-f have odd degrees.
Euler published this work in 1741 titled as the solution of a problem relating to the geometry of position. Königsberg's seven bridges problem and more related work formed the basis for modern branches of Mathematics called Graph theory and Combinatorial topology. Leibniz and Euler thought of Graph theory as the geometry of position. Likewise, modern mathematicians think of Combinatorial topology as the analysis of the position.
Comments