10 July 2017
Königsberg Bridge and The Graph Theory
You might be wondering what the connection that a bridge and mathematics has, but Königsberg Bridge is surely a special one


Königsberg was a city in medieval Germany and it had a unique geographic landscape. This city lay on both sides of the Pregel River. At the center, there were two large islands. The two islands were connected to each other and to the riverbanks by seven bridges. Then, Carl Gottlieb Ehler, a mathematician who was also the mayor of the nearby town, came up with this question: which route would allow someone to cross seven bridges without crossing any of them more than once?




You may try to answer that question, but unfortunately that is impossible. There is no way that one can cross all those seven bridges only once. This fact thrilled Leonhard Euler, the inventor of Graph Theory, whose then tried to explain the reason behind that impossibility. Euler simplified the map into four landmasses: south bank, north bank, island one, and island two. These landmasses were then represented as single points, which we call now as nodes, with line or edges between them to represent the bridges. With this simplified graph, we can count the degrees of each node (or the number of bridges each landmass touches). Why are those degrees so important? Since we can only cross a bridge once, it means that the bridges leading to and from each node should come in distinct pairs, which is then concluded that the number of bridges touching each landmass visited must be even. The only possible exceptions would be the locations of the beginning and end of the route. But we can see from the graph that every node has an odd degree. This answer was developed into the first ever paper on Graph Theory, Seven Bridges of Königsberg (1736). Since the publication of this paper, many mathematicians try to develop the theory that results in the Graph Theory we know today.