Answer all the questions on the question paper.

All answers must be written in pen, but drawings may be written in pencil.

The river Pregel runs through the town of Konigsberg. (Now Kaliningrad in Russia.) In the middle of the river are two islands connected to each other and the rest of the city by seven bridges. It became a town tradition to take a Sunday walk, and try to cross each of the seven bridges only once. No one had solved the problem until it came to the attention of the Swiss mathematician Leonhard Euler (1707 – 1783). Euler (pronounced “oyler”) was able to show that the feat cannot be done. And in the process of solving this problem he invented a new branch of geometry called topology.

Figure 1

Euler reduced the problem to a network of paths connecting the two islands and the sides of the river. In this project you will work with a variety of networks to see if you can come up with a rule to determine whether a network can or cannot be “traveled.” A collection of points connected by paths is called a network. When we say a network can be traveled, we mean that the network can be drawn in pencil without lifting the pencil off the page and without retracing any paths. (Note that the points can be passed over more than once.)

It makes things easier if you know that the number of paths is not important in determining whether or not a network can be traveled. So we will investigate the points. There are two types of points in networks: odd and even points.

Odd points:

These have an odd number of points leading to them.

Figure 2

Even points: These have an even number of points leading to them.

Figure 3

Consider the following networks and complete the table below. When you have completed the table, you should find that seven networks cannot be traveled.

Figure 4

Look carefully at networks L, M, N and P. These four networks have only even points. Notice that the network can be traveled whether you have one even point or seven even points, as long as there are no odd points. It appears that you can have as many even points as you desire and the network can be traveled. Therefore the odd points cause trouble. Study the table to see how the number of odd points determines whether or not a network can be traveled in order to make a conjecture.

Conjecture: A network can be traveled whenever...

It's a good idea to test your solution on some more examples. Let's look at some networks with odd points that we are able to travel (e.g. networks A, B, C, D, H.) Where did you start and where did you end? Did you start/end at an odd or even point? How did you travel them?

1) Below is a network diagram of the River Pregul and the two islands as shown in the information section. Draw an eighth bridge so that you can travel over all the bridges exactly once. Also include your start and finish in your diagram.

Figure 5

3) There are eight major roads in Euler country. A map is shown on the right. The lines on the road need to be repainted. The painter realises that they are going to need to go back along at least one of the roads (from what we have learned he is correct.) What is the shortest distance they must travel to cover the eight roads, starting and ending at point B? Describe the shortest distance; which road/s does he cross twice?

Figure 6

Shortest distance:

Can this lusona diagram be created by following one continuous path? If so, show how. If not, explain why not.

Figure 7

We will now consider the three parts of a network – number of points (P), number of regions (R) and number of paths or lines (L). Consider the same networks (A – P) from part 1. This time count the total number of points (P), the total number of paths (L) and the total number of regions (R) formed between the paths. When counting the regions it is important to include the region outside (around) the network.

Once you have completed the table search for a pattern that might lead to another conjecture. This time your conjecture will be a formula. By adding and subtracting you will find a formula that works for all networks. When you have found the formula, complete the following conjecture.

Conjecture: If P stands for the number or points in a network, L stands for the number of lines in the network and R stands for the number of regions in the network, then the equation that relates all three for any network is...

1) If a network has 26 points and 41 paths, how many regions does the network create?

2) If a network has 36 points and 19 regions, how many paths does the network have?

3) Draw a network that has 8 points and 10 regions (including the region around the network.) How many paths will you have to draw among the points?