The Seven Bridges

Date: 8/28/96 at 16:9:19
From: Anonymous
Subject: The Seven Bridges

There is a problem from the 1700s about a town with seven bridges, 
where you want to cross each bridge exactly once.

Date: 10/13/96 at 17:31:36
From: Doctor June
Subject: Re: The Seven Bridges

This is a famous problem that was sent to a mathematician named Euler 
(pronounced OILER). The people of Konigsberg wanted to know if they 
could cross all seven bridges exactly one time and end up where they 
started. Euler proved that it was not possible. Using Graph theory, 
think of the bridges as edges and the land as vertices. Being able to 
end where you started and crossing all edges exactly once is called an 
Euler Circuit. Being able to cross all edges, but NOT end where you 
started is called an Euler Path.  Can you figure out quickly when you 
can have an Euler path or circuit? 

Hint: think odd and even!

-Doctor June,  The Math Forum
 Check out our web site!  http://mathforum.org/dr.math/   

Date: 10/13/96 at 17:31:36
From: Doctor Chuck
Subject: Re: The Seven Bridges

Here's the problem: There are seven bridges that cross two islands, 
and either side of a river. Here's a quick drawing:

Pretend that the *** are water, and that BBB are bridges.

                                          |
                             *************B*******************
                           ***************B*******************
        |       |        ******           |
********B*******B*************
*****   |       |     ********              
****                =BBBBBBBBBBB=
*****   |       |       ********          |
********B*******B*************************B**************************
********B*******B*************************B**************************
        |       |                         |

These are very pretty bridges. The question arose, can a tourist cross 
all seven bridges in an afteroon without crossing the same bridge 
twice? 

We can draw this problem as a graph, with each vertex representing one 
of the pieces of land, and each edge being a bridge.
                                                          
      ...O.........                                                
      |  |         \                                                     
      \ /           \                                
       O.............O     
      / \           /                                                 
      |  |         /                                                    
      ...O.........                                  
                                                                           

It turns out to be impossible to make a cycle on this graph that goes 
over every path exactly once. You can look up a good discussion of 
these types of problems at:

http://www-groups.dcs.st-and.ac.uk/~history/HistTopics/Topology_in_mathematics.html   
               
Hope this helps,

-Doctor Chuck,  The Math Forum
 Check out our web site!  http://mathforum.org/dr.math/