In the eighteenth century the city we now know as Kaliningrad was
called Königsberg and it was part of Prussia. Like many other great
cities Königsberg was divided by a river, called the Pregel. It contained two
islands and there were seven bridges linking the various land masses. A
puzzle at the time was to find a walk through
the city that crossed every bridge exactly once. Many people claimed
they had found such a walk but when asked to reproduce it no one was able to. In
1736 the mathematician Leonhard Euler explained why: he showed that such a walk didn't exist.
Euler's solution is surprisingly simple — once you look at the
problem in the right way. The trick is to get rid of all
unnecessary information. It doesn't matter what path the walk takes on
the various land masses. It doesn't matter what shape the
land masses are, or what shape the river is, or what shape the bridges are. So you might as well
represent each land mass by a dot and a bridge by a line. You don't have
to be geographically accurate at all: as long as you don't disturb the
connectivity of the dots, which is connected to which, you can distort
your picture in any way you like without changing the problem.
Once you have represented the problem in this way, its features are
much easier to see. After playing around with it for a while you might
notice the following: when you arrive at a dot via a line (enter a
land mass via the bridge), then unless it is the final dot at which your
walk ends, you need to leave it again, by a different line as those are
the rules of the game. That is, any dot that is not
the starting and end-point of your walk needs to have an even number of
lines coming out of it: for every line along which you enter there has
to be one to leave.
For a walk that crosses every line exactly once to be possible, at most two dots can have an odd number of lines coming out of them. In fact there have to be either two odd dots or none at all. In the former case the two correspond to the starting and end points of the walk and in the latter, the starting and end points are the same. In the Königsberg problem, however, all dots have an odd
number of lines coming out of them, so a walk that crosses every
bridge is impossible.
Euler's result marked the beginning of graph theory, the
study of networks made of dots connected by lines. He was also able to
show that if a graph satisfies the condition above, that the number of
dots with an odd number of lines is either zero or two, then there
will always be a path through it that crosses every line exactly
The result also marked the beginning of topology, which
studies shapes only in terms of their connectivity, without taking
note of distances and angles. The London tube map is a great example
of the topological triumph. By distorting distances and angles it
turns what would otherwise be an unintelligible mess into a map that
every tourist can read effortlessly. You can find out more here.
About this article
This article was inspired by content on our sister site Wild Maths, which encourages students to explore maths beyond the classroom and designed to nurture mathematical creativity. The site is aimed at 7 to 16 year-olds, but open to all. It provides games, investigations, stories and spaces to explore, where discoveries are to be made. Some have starting points, some a big question and others offer you a free space to investigate.