Today is the 306th birthday of Leonhard Euler, a great mathematician who developed different insights not only in mathematics, but also in Physics disciplines like mechanics, optics and astronomy. He developed a lot of work in mathematics among which he stated the bases of Graph Theory and Topology.
It was solving a problem related with a circuit formed by seven bridges in Königsberg, city of Prussia (Now Kaliningrad Russia). This city was situated at the border of the Pregel River. As is showed in the figure below, inside the city there was a circuit of the river. This position made this city very important for commerce. In order to connect the city, the habitants built seven bridges that connect all the points of the city and allowed them to cross from one landmass to the other.
The problem started when in 1736 the mayor Carl L. Gottlieb wanted to have a circuit using the bridges such a way that starting from one point it be possible to cross for all the bridges only once. As in the Village they didn’t found a solution, the mayor asked Euler for help to found a solution.
Although Euler at the beginning didn’t accept to solve this problem, may be because he found this so trivial, he started to work in this because it seems to be related with some work in geometry that Leibniz had discussed in one of his publications and that called `geometria situs` i.e., “geometry of position”. This geometry of position derived in what we know now as Graph Theory.
Developing the mathematics needed to solve the problem, in 1735, Euler presented his paper called “Solutio problematis ad geometriam situs pertinetis“ in which he exposed the mathematical bases of Graph Theory.
In that paper he stated the general question to the problem: Can one find out whether or not it is possible to cross each bridge exactly once?
After his analysis and develop of this new mathematics, he found that this problem does not have solution, in fact he conclude that:
• If there are more than two landmasses with an odd number of bridges, then such path is impossible.
• If there are exactly two landmasses and the number of bridges is odd, then the path exists if it starts in one of the two odd numbered landmasses.
• If there are no regions with an odd number of landmasses then the path can be accomplished starting in any region.
In this paper Euler worked with vertices and edges as now a day are used in Graph Theory and Network Theory. That is why when a path in a graph use each edge of the graph once and only once, is called an Eulerian path.
Due the nature of the problem, and the simplicity of the solution using nodes and edges, this is a very important problem and initial point to start learning Graph Theory and Network Theory.