WHEC LECTURE

In this lecture, we shall look at some puzzles that you might have seen.

These puzzles have nothing to do with numbers but they are part of mathematics.

In fact,mathematics is not about numbers but about ideas.

You will need the handout that accompanies this lecture.

Page 1

Page 2

Look at Example 1.

Think of this as a street map.

The lines are the streets and the circles are the street intersections.

I have marked home with A.

This is what you have to do: starting at A walk down every street exactly once returning home.

You can go through any intersection as many times as you want but you are only allowed

to walk down each street once, and once only.

Can you repeat with Example 2 what we did with Example 1?

These two examples are not the same.

Why is that?

We shall formulate a conjecture in a moment. First, we need a definition.

We
say that a map is
Eulerian if we can find
a circular walk that visits every street exactly
once. |

A map is Eulerian precisely when there are an even number of roads at every intersection (and the map must be connected: this just means

that there are no islands).

Do you think this map is Eulerian?

Observe that every intersection has an even number of roads.

Here is one I did earlier...

Actually, this is from a colleague's website.

In fact, our conjecture above really is a theorem.

How to find the walk that does the trick will be the subject of lecture 2.

Suppose now that I vary the question a little.

This time I select A as your starting point but B as your finishing point.

As before, you are only must walk down each street exactly once but this time you begin at A and finish at B.

We
say that a map is
edge-traceable from A to
B if we can find a walk that starts at A, finishes
at B and visits every street exactly once. |

In the lecture, I explained how to show that Example 4 is edge-traceable in such a way that leads to a proof of the following.

(and the map is connected).

This is called

It must be edge-traceable (by our Theorem), but how to show this is left as homework.

These puzzles have real-life applications in

- Laser cutting of materials.
- The study of DNA in biology.