The Königsberg Bridge Problem
Graph theory is uniquely suited to talking about maps and traveling. The Köngisberg Bridge Problem, which dates back to 1736, was one of the first examples of graph theory in action.
What You Should Learn
In 1255 Teutonic knights founded a city at a spot where the river Pregel branches and called it Königsburg. Over time bridges were built crossing back and forth across the various branches of the river in a manner similar to the figure to the right. Eventually, the citizens of Königsburg asked a question: Is it possible to walk around the city in such a way that you cross every bridge once and only once?
The problem itself isn't a particularly challenging one. If you spend a minute looking at the diagram you can probably figure it out through trial and error. What's kept it alive over the centuries is its use as an example of mathematical modeling. The second figure on the right shows how the real world map can be "translated" into the edges and vertices we've been using in our earlier diagrams. In this case the edges represent the bridges and the vertices are the islands and the river banks. I've labeled the islands i1 and i2 and the river banks b1 and b2 to make it clearer what they represent. If you had difficulty answering the question about the existence of a walk in the last paragraph, try it again using the graph theory diagram. One of the goals of creating a mathemtical model of a real world situation is to simplify it - paring it down to only the parts that you really need to see to answer questions.
Leonhard Euler and the Solution
The Königsberg Bridge Problem was originally solved by a Swiss mathematician named Leonhard Euler. (His picture is at the bottom left of the page.) The answer to this specific problem is "no" but what makes Euler's work interesting is his solution to a more general question: Say we have a connected graph. (We'll talk more about what exactly "connected" means in the next section.) Is there a way, other than trial and error, to tell if it's possible to "walk around the graph" so that each vertex is crossed exactly once? The answer to that question is "yes":
If G is a connected graph then there exists a "path" that crosses each edge exactly once if and only if there are at most two vertices whose degree is odd.
I'll spare you a formal proof of this. It's not particularly complicated but it is a little lengthy. Instead let me try to give you a non-technical explanation. Let's say you're walking around a graph and you arrive at a vertex. If this you still have edges left to cross then there has to be a way off of the vertex. In other words, for every edge that takes you onto a vertex, there has to be an edge taking you off of the vertex. Another way of saying this would be, "The degree of the vertex has to be a multiple of two." But that's just the definition of an even number. The only exception to this is the vertex at which you start and the vertex at which you finish. Since you never have to go back into the starting vertex and you never have to leave the ending vertex it's okay for each of those to have an odd degree.