### Find a Route That Crosses Each Bridge Exactly Once

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