Introduction to graph theory

Graph theory and the idea of topology was first described by the Swiss mathematician Leonard Euler as applied to the problem of the seven bridges of Königsberg. Königsberg consisted of four islands connected by seven bridges (Figure 2).  No one had ever found a path that visited all four islands and crossed each of the seven bridges only once. Naturally, people assumed that no such path existed, but there was no mathematical proof of this.

Figure 2 The seven bridges of Königsberg. Images are from Wikimedia Commons and used under Creative Commons Attribution-Share Alike 3.0 Unported license. 

Euler showed that, to solve the problem, only the relations between the land masses are relevant, not the shape or actual distances on the map. These relationships can be represented in the form of a graph where the land masses are the nodes and the bridges are the edges of the graph. Euler used this graph and its topological features to prove that the path did not exist.

Euler’s formulation of this problem provided the basis of a whole area of mathematics and it is the foundation of all the tools and concepts we will explore in this course.

You can read more about Euler’s solution to this problem on Wikipedia (2).