Return to my Puzzle pages
Go to my home page
© Copyright 1999, Jim Loy
Here is a
diagram of the city of Königsberg (now called Kaliningrad). It is on both
banks of the river Pregel, as well as on two islands. And it had seven bridges,
as shown. Some people speculated that there might be some path through the
city, which would cross all seven bridges only once. People tried this, but
never succeeded. Leonhard Euler (pronounced "oiler") showed that it
was impossible, and thus created Graph Theory.
The proof that the path is impossible goes like this. Look at the island on the right. There are three bridges connecting this island to elsewhere. If our path begins on this island, then it leaves the island, comes back, and then leaves the island, using all three bridges in some order. Fine. If our path starts elsewhere, it eventually comes to this island, leaves it, and then comes back. We have shown that our path either starts here or ends here. One of the endpoints of our path is on this island. The same holds for the northern shore and the southern shore. One of the endpoints must be in the northern part of the city, and one endpoint must be in the sourthern part of the city. Our path cannot have three endpoints. So the path is impossible. In fact we can show that the left island must also contain one of the endpoints. Any area connected to an odd number of bridges must contain one of the endpoints.
The
above picture of Königsberg is equivalent to the graph on the right. The
bridges are represented by the edges of the graph. Such a graph, and the above
observation that any vertex (area of the map) connected to an odd number of
edges (bridges) must contain one of the endpoints, simplify the solution to
many puzzles.
Here is a
puzzle. We have the black boxes on the left. Our task is to draw a path (the
one in red is just beginning) so that it goes through each wall only once. Each
wall is the black line between two wall intersections. The upper right box,
therefore, has five walls which must be crossed. Our path cannot go through an
intersection. This is very similar to the Königsberg puzzle. The walls are
exactly like the bridges. In this puzzle, three of the areas (vertices) have an
odd number of walls (bridges or edges). And so our path must have three
endpoints, and is impossible. Two of the vertices have an even number of edges,
and are no problem. If the puzzle had had a solution, i.e. if the path has two
or fewer endpoints, the graph would tell us where those endpoints must be, and
the solution would become simple. If the graph specifies fewer than two
endpoints, then we can put the unspecified endpoints anywere we want.
On the right is
another common kind of puzzle, which produces a similar graph. Can you draw
this figure without taking your pen (or pencil) off the paper, and without
crossing your line. Examining the diagram, we see two vertices (intersection
points) that have three edges. These must be the two end points of our path.
The puzzle is fairly easy with that information.
See also Four Color Theorem Intro and Cannibals and Missionaries, etc.