The Network Origins of Modern Graph Theory
https://www.maa.org/sites/default/files/pdf/upload_library/22/Polya/hopkins.pdf
https://www.math.ku.edu/~jmartin/courses/math105-F11/Lectures/chapter5-part1.pdf
When discussing graph theory in class, it has been referred to as a tool to help visualize and analyze various examples of networks, such as social networks, road networks and ecosystems. However, the networks and the resulting analyses performed on them have not been conducive to discovering deeper properties which can’t be easily gleaned by the naked eye, and require some thought or more complex analysis. We have yet to look at graphs which aren’t solely concerned with the immediate relationships between nodes and from which we can extract more interesting conclusions. In this blog post, we aim to provide an example of such a deeper analysis of a network. The example in question is a famous problem in mathematics that arose in the 18th century, and it is often attributed as being the inspiration for the development of graph theory as a new field of mathematics. So the problem really shows how graph and network theory are really intimately connected (no pun intended!).
The problem itself is as follows (described in the first link above): the Prussian city of Königsberg (modern day Kaliningrad, Russia), had the Pregel River running through it. On the river there were two large islands that were connected to each other, as well as the mainlands, by several bridges as in the picture below (A and D are the islands and B and C are the mainlands). Is it possible to devise a stroll through the city such that the only way to the islands is by the bridges, and each single bridge would be traversed fully and exactly once? The set of islands and mainlands with the bridges clearly forms a network, similar in nature to the U.S. Interstate Highway System. This problem is known as the Seven Bridges of Königsberg, and as it turns out, there is no solution to it. This conclusion was first rigorously proven by the great mathematician Leonhard Euler; but contrary to popular belief, he did not actually use graph theory to solve the problem, as it did not exist yet. Nor did he invent it in his solution. Indeed, his solution may be regarded as more combinatorial in nature; but it did include statements that are somewhat reminiscent of a discussion about nodes and edges connecting them. As the second source points out, Euler’s crucial realization was that the physical layout of the city is irrelevant, and what really matters are the regions and the connections between them. Smells like graph theory! This is the crucial step towards graph theory, where the actual physical layout of a network (if it is physical) doesn’t matter; what matters are the connections between the components of the system. That is, in the language of graph theory, the edges and the nodes/vertices. It was this realization, and some concurrent developments in mathematics that eventually led to graph theory taking on the form it has today in the late 19th century.
The Seven Bridges of Königsberg asks deeper questions than the one we have encountered in class so far. One is a question of existence, and the other of optimization. Is there such a path? And if yes, what is the shortest one? Euler’s solution, as well as modern proofs using graph theory are able to provide answers to these questions. But graph theory provides the answer using an easier way, since we can now visualize the land masses as nodes in the network connected by edges that correspond to the actual bridges. Since we may ask more insightful questions, we may also get more insightful answers. So the Seven Bridges of Königsberg is an example of where we may use graph theory for more interesting and complex purposes.
