# The premature state of “Topology” and “Graph Theory” nourished by “Seven Bridges of Königsberg Problem”

December 16, 2017  2982 words 14 mins read

Many many years ago, there was a problem which created a mind-boggling puzzle to the eminent mathematician named Leonard Euler. But this isn’t the main starting of our story. There was a historical city of Königsberg in Prussia but after World War II, it has been named as Kaliningrad of Russia. Well, I’m not trying to make this story by creating some sad mood but it is the starting point where the problem was created. In that city, there is an island, called the kneiphof; the river (Pregel) which surrounds it is divided into two branches, and these branches are crossed by seven bridges [1]. Usually, in the evening time, the people who lived in this city used to gather near to the bridges and entertain themselves. These bridges act as a junction for them. The most entertaining things to them were the seven bridges of that city. Can you guess, how? They were trying to devise a route around the city which would cross each of the seven Königsberg bridges just once and only once. Every time they went to the junction and returned with no answer to that problem. Their ego was hurt badly. Some of them said, there is no any path to cross all bridges at once but they don’t have any concrete ideas to support it. And, many of them believed that the task was impossible. But it was not until the 1730s that the problem was treated from a mathematical point of view and the impossibility of finding such a route was proved [2].

Finally, the problem was given to Euler. As he was trying to give some thoughts in that problem, he saw it has a little link with mathematics and he added, its discovery doesn’t depend on any mathematical principle [3]. Again, he was trying to catch which known mathematical principle can be applied. His good luck! He got some clue. The clue was very simple; he stated, this is a geometry problem with no relationship with distances or angles. How can it be a geometry problem which does not have any relationship with distances or angles? As he was trying to understand the problem, he realized there’s the only relationship with bridges, lands, and rivers. He went through the primitive definition of Geometry. Have you ever stated the primitive definition of Geometry? I’ll say, it is a pure branch of mathematics that deals with points, lines, curves, and surfaces. The geometry which we were taught in elementary classes was Geometry of magnitude. He begins to thought bridges as curves or lines and lands as points. And, this is an elementary concept to start with Graph Theory. So, he laid the foundations of Graph Theory. He created the notion that you can start from any of the given bridges. So, he thought that the point where you start acting like the position where you situate. Because you can get the same result from a different position. So he claimed that it should be the problem related to the Geometry of Position. He was aware that, he was dealing with a different kind of geometry where it doesn’t involve measurements and calculations. This kind of geometry was defined by Leibniz and it was in the primitive phase in Euler’s time. Though Leibniz initiated this concept, there wasn’t such a problem that can be solved by this concept. But, Euler found the problem that can be solved by this concept. Today, we call it Topology. This concept suggested that how things connect one to another. It is especially concerned with space and it also studies how properties of a space change and don’t change when space is distorted. In this problem, it doesn’t depend upon either the bridges are long or short, either the position where you start is farther or nearer from the bridges. The points which are concern with the land is actually a position of an experimenter. And the point can be specified in any place within the specific land. In 1736, Euler published a paper on the solution of the Königsberg bridges problem entitled “Solutio problematis ad geometriam situs pertinentis” which translates into English as “The solution of a problem relating to the geometry of position” [4]. His original paper was first published in Commentarii academiae scientiarum Petropolitanae 8, 1741, pp. 128-140 [7] and it was the first journal series published by the St. Petersburg Academy [8]. In this paper, he proved the problem has no solution. The difficulty was the development of a technique of analysis [5] and to establish the general method to compute not only that problem but others too.

Now, we are dealing with “How Euler solved the Königsberg bridge problem?” and some basics of Graph theory. In Euler’s original paper, He was asked as “Whether anyone could arrange a route in such a way that he would cross each bridge once and only once?” [2]. Here, I’ll be discussing only two methods out of three, if you want to read the last method then, you can prefer reference 2 that is mentioned in the section “References”. Also, I’ll be pointing each and every step, analysis, results and conclusions that he made and, make you simple to understand. Step I: First, we have to give notation to the seven bridges and four land areas. Here, we gave notation to seven bridges as a, b, c, d, e, f, g and four land areas separated by rivers as A, B, C, D and also, replacing the map of the city into simpler diagram showing only river, bridges and lands which is exactly done by Euler.

Analysis I: He formulated the general problem as, “Whatever be the arrangement and division of the river into branches, and however many bridges there be, can one find out whether or not it is possible to cross each bridge exactly once?” [2]. Step II: He said, If you go from A to B over bridges a or b, you can write as AB where the first letter says you are leaving from this place and the second letter says you are entering in this place. Similarly, if you leave B and crosses into D over bridge f then, it can be represented by BD. If you would like to cross AB and BD, it can be represented by the three letters ABD where the middle letter B refers to both the area which is entered in the first crossing and to the one which is left in the second crossing. Then, if you go from D to C over the bridges g, it can be represented by four letters ABDC which says you started from A, crossed to B, went on to D, and finally arrived in C. Result I: Hence, the crossing of three bridges gave us four letters and, the crossing of four bridges would give five letters. In general, how many bridges the traveler crosses, his journey is denoted by a number of letters one greater than the number of bridges. So, the crossing of seven bridges requires eight letters to represent it. Conclusion I: Thus, we have to use four letters (i.e. ABCD) in order to represent the possible paths with eight letters. Analysis II: We are now trying to find such a rule whether or not such an arrangement can exist. Also, we are trying to find what is the number of repetition of a letter A that will appear when we cross an odd number of bridges (i.e. five bridges in our case) from the A or into the land A? Step III: Let’s make our diagram simple, we will make a river with no branches in it and, which separate the land areas A and B. We put six bridges over the river.

Any feedback?

If you guys have some questions, comments, or insults then, please don’t hesitate to shot me an email at damodar[at]physicslog{dot}com or comment below.

Liked this post?