Koenigsberg

   
Recent changes
Table of contents
Links to this page
FRONT PAGE / INDEX

images/KoenigsbergBridges.png
In the town of Koenigsberg there was a river with two islands and seven bridges. Each Sunday people would go for a walk. After a while someone noticed that no matter where they started they were never able to cross each bridge once and only once during their walk. It seemed that no matter where they started and where they walked, they would always end up in the wrong place for crossing that last bridge.

Try it for yourself.

It was suggested that perhaps it was impossible, but there was always the nagging doubt that perhaps it was possible and people simply hadn't (yet!) found how to do it.

Then along came a clever chap called Leonhard Euler (pronounced "Oiler") who settled the matter once and for all. In doing so he used the main ideas found in all mathematics:

Abstraction

images/KoenigsbergGraph.jpg
The first thing that Euler did was to say that several things didn't matter. The shapes of the islands, the lengths of the bridges, the distances between the bridges, and so on. He threw away these irrelevant details and ended up with a much simpler diagram:

Because walking around on land or islands was irrelevant, he shrunk each of them to a single point, leaving only the lines representing the bridges.

Now observe that if you can draw this diagram without lifting your pen and without going over any line twice, that gives you your Sunday walk.

Reasoning

There are four meeting places, here labelled A, B, C and D, and all of them will have to be visited on our walk. You might start at one and finish at another, but there will always be at least two of them that are neither start nor finish. Let's pick one to think about, we'll call it X.

Since X has some bridges coming to it we will have to visit it at least once. Since we neither start nor finish there, every time we come in we must go out again, and on a different bridge. That means that the total number of bridges that land at X must be even. For every in there is an out, and if there's an odd number of bridges, that won't work.

So X, our place that is neither start nor finish, must have an even number of bridges. However, all our landing places have odd numbers of bridges,and that makes it impossible to do our walk.

Generalisation

Of course, in the specific case of Koenigsberg it's not that difficult to try all the possibilities and convince yourself that it's really not possible. However, the reasoning outlined above has opened the door to much, much more. We have shown that:

We might wonder:

This is one of the topics that can be given as a mathematics talk.

Contents

 

Links on this page

 
Site hosted by Colin and Rachel Wright:
  • Maths, Design, Juggling, Computing,
  • Embroidery, Proof-reading,
  • and other clever stuff.

Suggest a change ( <-- What does this mean?) / Send me email
Front Page / All pages by date / Site overview / Top of page

Universally Browser Friendly     Quotation from
Tim Berners-Lee
    Valid HTML 3.2!