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!  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/

```
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
Math Forum Home || Math Library || Quick Reference || Math Forum Search