The Königsberg Bridge Problem

The city of Königsberg is divided by a river that contains two islands. The various parts of the city are connected by seven bridges. The Königsberg Bridge Problem is: can you make a tour of the city that crosses each bridge once and only once?

Leonhard Euler, whose towering awesomeness in mathematics is almost beyond the comprehension of mere mortals, solved this problem and invented the fields of graph theory and topology at the same time by representing the city in terms of "nodes" (places you can be in the city) and "edges" (the paths you take between them) as such:

Image from Wikipedia.

Now look at any of the nodes with three edges. If you begin at such a node, you leave by one edge, return by a second, and leave by the third. This turns out to be the case if the number of edges is any odd number. But if while on your journey you enter such a node, you leave by the second edge, but eventually must return by the third and end your journey. Again, this is true of any node with an odd number of edges. Euler used this observation to determine that to traverse each edge once and only once the number of nodes with an odd number of edges must be either zero or two - and in the latter case, you must begin and end at the nodes with the odd numbers of edges. Since this is not the case with the Königsberg bridges (all four nodes have an odd number of edges) the problem has no solution; it is not possible to cross each bridge only once.

This is the first in what may become a long series of "homework help" posts. If your dad is a professor and you ask him a question about your schoolwork, chances are you'll get a lecture in return. Make sure you cite your sources!