The Seven Bridges of Konigsburg

The river Pregel runs through the town of Konigsburg. In the river are two islands, connected to each other and the rest of the city by seven bridges.

The students of Konigsburg often challenged each other to try to make a trip crossing all seven bridges exactly once. Take a moment to see if you can trace a path which crosses each of the bridges exactly once (no swimming allowed).

Can you trace the following figures without lifting your pencil or tracing any line more than once? If you can, mark your starting point with an S and your finishing point with an F.

We call these figures networks. Any place where two or more lines meet or intersect is called a vertex. If there are an even number of lines coming from a vertex, then that vertex is even. If there are an odd number of lines coming from a vertex, then that vertex is odd.

Now we will try to find a way to predict which networks can be traced and which networks we cannot trace. We will also look for clues about the best place to start tracing.

  1. Circle all the odd vertices in the above networks.
  2. For each network, count the number of odd vertices and the number of even vertices, then complete the table below.

Network
No. of even vertices
No. of odd vertices
Can it be traced?
(a)

(b)

(c)

(d)

(e)

(f)

(g)

(h)

Using the information in this table, answer the following questions:

  1. Can a network with no odd vertices be traced?
  2. Can a network with two odd vertices be traced? Did you start at an odd or even vertex? Did you finish at an odd or even vertex?
  3. Can a network with more than two odd vertices be traced?
  4. Based on your previous answers, how would you suggest we determine if a network can be traced?
  5. Create several networks of your own. Does your method accurately predict whether they can be traced?

The students of Konigsburg asked Leonard Euler, a famous mathematician to help them determine if it was possible to cross each of their seven bridges exactly once. Euler used networks to solve this problem.

  1. Draw a network that represents the two islands and seven bridges. Each island and the two river banks are vertices. Each bridge is a line connecting two vertices.
  2. Using the method you determined above, determine whether it is possible to cross each bridge exactly once.