In Euler's footsteps
WHEC LECTURE
22nd November 2016
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
Sketch lecture notes

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.

This turns out to be easy.


Now look at Example 2.
Can you repeat with Example 2 what we did with Example 1?

This appears to be impossible.
These two examples are not the same.

Why is that?

We observed that in Example 1 every intersection had an even number of roads whereas in Example 2 some intersections have an odd number of roads.

This is significant.

At each intersection, we must leave by a different road from the one we entered. When there are an odd number of roads this is impossible.

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.


The word Eulerian is taken from the name of the mathematician Leonhard Euler who first studied this question.

Conjecture (something we believe to be true but have yet to prove).
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).
Now look at Example 3.
How confident are you in our conjecture?
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.
Look at Example 4.

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.

Theorem. A map is edge-traceable precisely when there are exactly two intersections with an odd number of roads
(and the map is connected).


Now look at Example 5.
This is called Listing's pattern.
It must be edge-traceable (by our Theorem), but how to show this is left as homework.
These puzzles have real-life applications in