The Origins of Graph Theory
Graph theory is a sub-discipline in Mathematics that studies graphs and their properties. Graphs are fascinating! With graphs we can represent connections or interactions between objects or other complex systems.
How and why did mathematicians start studying graphs?
We can thank Leonhard Euler!
Euler was a prolific scientist from the 18th century. His work spans from mathematics, astronomy to physics and engineering. Among his contributions is the foundations for what we call today graph theory.
Born in Switzerland, Euler spent part of his academic life at the Imperial Russian Academy of Sciences, in St. Petersburg.
Königsberg was a city in the Prussian Empire, the area that now is Kaliningrad, in Russia. It was founded in 1245 to take advantage of its strategic positioning. The city is surrounded by the Pregel river, now referred to as Pregolya river, as if protected by the walls of a castle. The river divided the city into four regions, connected by seven bridges.
The story goes that citizens of Königsberg enjoyed relaxing Sunday strolls around the city. At the time the Königsberg had become an important trading center. So some people started wondering if they could walk all around Königsberg passing though each bridge only once and make it back to where they started.
This question sparked a lot of curiosity! So much that in the 1730’s, Euler wrote a paper proposing a solution to what we call to the “Seven Bridges of Königsberg Problem”.
In his solution, Euler started by abstracting the problem. He realized that it wasn’t necessary to distinguish between the parts of the city. What was important was how areas were connected among each other via the different bridges.
Even though his approach was to solve this as a geometric problem, Euler's solution was the breeding ground for modern Graph Theory.
Representing the problem as a graph, the circles represent the different parts of the city. The lines connecting them are the bridges. The Königsberg graph has 4 nodes and 7 edges. It is also an undirected graph, which means that there is no predefined direction to how, say edges A and B, are connected. You can walk from A to B or from B to A.
As a true scientist, Euler applied the Scientific Method. The initial hypothesis was something like “One can traverse each bridge only once, for any walk starting and ending in any given part of the city”. Euler analyzed how some parts of the city were more connected than others. He then concluded that the hypothesis was impossible. The geometry of the city didn’t permit the hypothesis to be true. If you you want to walk across every bridge in Königsberg you’ll have to visit some parts of the city more than once.
We can try the exercise ourselves and, for instance, try to traverse every edge in the graph starting in node D. We'll see that, to start and finish the walk at node D, we'll have to visit some nodes multiple times.
What started as a curiosity and a real-world problem, efficiently traverse each bridge in Königsberg, became an extremely important scientific discipline.
The fascinating part is that we all take advantage of graph theory and its applications almost every day. When we use a maps app and obtain the fastest route to our destination. Or when we search online, leveraging on the fact that information on the web is organized as a gigantic graph of webpages.
Thanks for reading!
