Math 300

Groupwork

Find a Route That Crosses Each Bridge Exactly Once

Dr. Wilson

A city is built on three islands in the delta of a river, and it also extends to both sides of the river as in the map below.

 

 

 

 

 

If possible, find a route through the city which traverses each bridge exactly once. You may end at the same point from which you started, but it is not necessary. All you have to do is to cross each bridge once before you cross any bridge a second time. If it is not possible, state why.

 

There are several possible paths which will cross each bridge exactly once. Here is one

 

 

The thing to notice in these problems is the number of bridges from each region.

 

 

Notice that if a region has an odd number of bridges, then if a path starts outside of the region and crosses all of the bridges, then it must end inside the region, and if a path starts inside the region then it must end outside of the region. If, on the other hand, the region has an even number of bridges, then if a path starts outside of the region, then it must end outside the region, and if it starts inside the region, then it must end inside the region.

 

As a result, a necessary condition for there to be a path that crosses all the bridges, either all of the regions must have an even number of bridges, in which case such a path would end in the region where it started, or it must have exactly two regions with an odd number of bridges, in which case the path must start in one of the regions with an odd number of bridges and end in the other, as we see in our example above.

top

Groupwork