Blogpost 5: The inception of Graph Theory

The beginnings of Graph Theory is usually traced back to the mathematician Leonhard Euler, who in 1735 solved the famous "Konigsberg bridge problem". The question at hand was " is it possible for the people of Konigsberg to walk around the city, crossing all seven bridges only once, and the person or persons walking do not have to end up from where they started walking from".

(A map of Konigsberg and the seven bridges (in red) connecting the land, picture from www.maa.org )

Euler thought of this problem as trivial, however he stated that
 " This question is so banal, but seemed to me worthy of attention in that [neither] geometry, nor algebra, nor even the art of counting was sufficient to solve it" (www.maa.org/leonard-eulers-solution-to-the-konigsberg-problem).
What Euler did from here was one of the many reasons he is considered one of, if not the greatest mathematician of all time.
Euler determined that choosing a route within each land mass was irrelevant. The only important aspect of route choice was the sequence of bridge crossings. This thought process allowed Euler to reformulate the problem in abstract terms (laying the foundations of graph theory), eliminating all features except the list of land masses and the bridges connecting them (Pickover, C, "The Math Book). Euler replaced the map of the city by a much simpilar diagram showing only the main features. In modern graph theory, this diagram is further simplified using "dots", which are referred to as vertices (or nodes), and line elements that are usually referred to as edges. Below is a graph that represents Euler's new viewpoint of the map and a modern graph theory representation.

                                                                         (Euler's representation of Konigsberg city)                                    

                                           (modern graph theory representation.image from  www.kurzweilai.net)   

The relationship between vertices and edges is called a graph. Euler felt that this problem was one that was related to a topic that was once discussed by Gottfried Leibniz called "geometry of position". This so called geometry of position that Euler used is what is referred to today as Graph Theory. Today, graph theory serves many purposes;finding communities in networks (for example, social media networks like Facebook and Twitter), GPS systems in order to find the shortest route home, postal services, and many other purposes including many other applications in computer science.
We cannot discuss the inception of Graph Theory without taking a very simplified look at Euler's proof of  the Konigsberg bridge problem.......

Euler realized that, excluding where the person ends their walk, whenever one enters a vertex by a bridge, one leaves a vertex by a bridge. In graph theory lingo, during any walk in the graph, the number of times one enters a non-terminal vertex equals the number of times one leaves it. Now, since every bridge has been crossed exactly once, for each land mass that was reached (excluding the ones that were chosen for the start and finish of the walk), the number of bridges touching that land mass must be even. However, all four of the land masses in the original problem (see picture above) are touched by an odd number of bridges (one is touched by 5 bridges, and each of the other three is touched by 3). Since, at most, two land masses can serve as the endpoints of a walk, the proposition of a walk crossing each bridge only once leads to a contradiction, and therefore, the walk is not possible.

Euler did figure out what layout would be required in order to complete such a walk for any number of bridges and land masses. Euler figured out that in order to complete a walk of this desired form, a graph must be connected and have EXACTLY zero or two vertices of odd degree, meaning that out of all of the land masses and bridges that connect them, there can only be two land masses or zero land masses that are connected by an odd number of bridges for this walk to be possible. Pretty dang awesome!