The Math Forum

Ask Dr. Math - Questions and Answers from our Archives
Associated Topics || Dr. Math Home || Search Dr. Math

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!   

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.

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

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

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

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:   
Hope this helps,

-Doctor Chuck,  The Math Forum
 Check out our web site!   

Associated Topics:
High School Discrete Mathematics
High School History/Biography
Middle School History/Biography

Search the Dr. Math Library:

Find items containing (put spaces between keywords):
Click only once for faster results:

[ Choose "whole words" when searching for a word like age.]

all keywords, in any order at least one, that exact phrase
parts of words whole words

Submit your own question to Dr. Math

[Privacy Policy] [Terms of Use]

Math Forum Home || Math Library || Quick Reference || Math Forum Search

Ask Dr. MathTM
© 1994- The Math Forum at NCTM. All rights reserved.