by Andrew Boyd
Today, the bridges of Königsberg. The University of Houston's College of Engineering presents this series about the machines that make our civilization run, and the peoplewhose ingenuity created them.
I first encountered the problem in elementary school. I was on a field trip to the Seattle Science Center. One of the instructors there showed us a picture. On it were four islands. Some were connected by bridges — seven in all. And she gave us a challenge.
"Pick any island," she said, "and see if you can find a walk that goes over every bridge exactly once and brings you back to the island where you started." I tried one walk, then another. No luck. I always had to retrace at least one bridge. I drew the picture on a piece of paper and took it home to show my parents. The instructor had succeeded. She'd made me think.
I ran into the problem many years later in a college course on graph theory. To mathematicians, a graph is a collection of islands connected by bridges or, more precisely, points connected by lines. Get a sheet of paper. Draw some points. Connect some of them with lines. You've got what mathematicians call a graph. Pretty simple. But graphs turn out to be remarkably interesting.
Many mathematicians make their living trying to solve difficult, abstract problems about graphs. Claws. Odd holes. Odd anti-holes. Graph theorists speak a language of their own. But graph theory has plenty of practical problems, too.
For example, street maps define graphs. We can think of each intersection as a point and each street segment between two intersections as a line. So the problem of finding a shortest path from your house to work is a problem in graph theory. So is the problem of picking good bus routes, or how to make scheduled deliveries from a warehouse. Can garbage trucks be routed so they don't go down a street more than once? Graph theory again. In fact, it's just the island-and-bridge problem stated more generally.
The specific island-and-bridge problem I'd learned as a child is called the Königsberg Bridge Problem. As the story goes, it was posed by the citizens of Königsberg, Prussia, as they puzzled over the problem on their evening strolls. The problem was solved by the great mathematician Leonhard Euler in 1736. That moment's considered the beginning of graph theory. And the problem's solution is so simple — so satisfying — it's story has been passed down through generations of mathematicians.
Euler showed that every walk in Königsberg must retrace at least one bridge. But he also realized there's a simple way to tell if any graph does or doesn't have a walk free of repeated bridges. The answer? There's a walk free of repeated bridges if, and only if, every island is connected to an even number of bridges. Try to convince yourself — and your friends; or visit the Engines web site for a little help.
I'm Andy Boyd at the University of Houston, where we're interested in the way inventive minds work.
An updated version of this episode can be found at 3176.
For related episodes, see 1897, Optimization, and 2153, Cliques and Ties.
The land masses in the Königsberg Bridge Problem aren't all islands, as the picture suggests. They are simply land masses separated by a river, but were referred to as islands for audio clarity.
Euler went on to prove many facts about graphs. Here's how he reasoned the "even number of bridges" property.
Statement: If there exists a walk that starts and ends at the same point without retracing any lines, then each point must be connected to an even number of lines.
To see this is true, pick any point with an odd number of lines attached to it. Any walk that traverses every line must, in particular, traverse all the lines attached to this point. The walk visits this point on one bridge, then leaves on another, revisits the point on a different bridge, then leaves on another bridge, and so on (the walk can certainly go elsewhere in between the visits, but we don't need to know where to make our argument). At some point, because the number of bridges connected to the point is odd, the walk enters the point but can't leave — unless a bridge is retraced. (If by chance the point we picked was the starting point of the walk, the walk would eventually leave the point but couldn't return without retracing a line.) So we can conclude that every each point must be connected to an even number of lines.
Statement: If each point is connected to an even number of lines, then there exists a walk that starts and ends at the same point without retracing any lines.
Draw a walk at random, starting at any point. Because every point has an even number of bridges connected to it, you'll never get stuck at a point until you return to where you started. If you've traced all the lines, great; you're done. If not, call the walk you just created Walk 1. If you erase all the lines in Walk 1, the points and lines that remain have the property that each point still has an even number of lines attached to it. Call this graph with some of the lines erased Graph 2. So pick a new point P — one that's in Walk 1, and again create a random walk on Graph 2. Call this Walk 2. Notice that you can combine Walk 1 and Walk 2 by taking Walk 1 to point P, "inserting" Walk 2, which starts and ends at P, and completing Walk 1. Call this Walk 3. Now repeat the procedure by erasing all the lines in Walk 3 (which are all the lines in Walks 1 and 2). You may have to repeat the process a number of times, but since there are only a finite number of points and lines, the process must eventually stop.
The process sounds harder than it is. Give it a try!