All fired up

Finding paths through networks in which each section is used once only is a task that fascinates many students. It has the appeal of a maze, although it is very different. Students can quickly learn that the start and finish points for travelling through the network can be found by inspection rather than by trial and error. Furthermore, a simple rule can determine whether or not the problem can be solved at all!

Leonhard Euler, pronounced “Oiler”, (1707–1783) is the father of graph theory, a mathematical discipline that includes networks. He lived in Königsberg, Prussia, where the Sunday afternoon pastime was to walk over the seven bridges of the Pregel River.

The diagram below models the Königsberg bridges network.

A challenge for walkers was to cross every bridge once and once only and to end up at their starting point. Euler proved that this was impossible and, in doing so, developed a branch of mathematics that is used for modelling all sorts of situations, such as the smoke-filled buildings in this activity.

In this activity, the students are trying to find a path that goes through every tunnel once only. This is known as an Euler path. (If you had to return to your starting point as well, you would be looking for an Euler circuit.)

From a teaching point of view, it would be good to let the students initially attack the problem using trial and error. They may find it helpful to strip the diagrams of all unnecessary details, re-drawing them as lines and nodes. Once Euler paths have been identified, ask the students to identify why these paths work and others don’t.

Other possible questions include:

• “When a path is found, does the starting point (or node) of the network have an even number of tunnels connected to it or an odd number?”
• “Does the ending point (or node) of the network have an even or odd number of tunnels connected to it?”
• “Do all other nodes in the network have an even or an odd number of tunnels connected to them?”

The answers to the above questions give the basic rules for finding Euler paths and circuits through any network. These are:

• For a network to have an Euler path, the start and finish nodes must have an odd number of paths connected to them. All other nodes must have an even number of connecting paths.
• For a network to have an Euler circuit (a path that begins and ends at the same point), all the nodes must have an even number of paths.

Using these rules, we can look at any network and quickly determine whether or not it has an Euler path and, if so, where to start.

As an extension, the students can draw their own networks using these simple rules. You can also ask:

• “What could be done to the Königsberg bridge problem to make it an Euler path and then an Euler circuit?”

A further extension task is to challenge the students to create a series of networks that have an identical structure but that look very different, as in the following examples (note that shape means nothing; structure is everything!):

1.

Possible routes are:

2.

Drawings of buildings will vary.