The Prussian city of Konigsberg now the Russian city of Kaliningrad is situated on the banks of the
river Pregel. The land masses were seperated by this river and connected by bridges to each other.
The citizens of this town wondered if it was possible to cross all the bridges without revisiting a bridge already
crossed. They all tried, but in vain. Nobody could find a route which would cross all the bridges only once.
As can be seen from the map, all land areas (A, B, C and D ) are seperated by the river.
The bridges (b1 to b7) connect the land areas. In the river there are two islands D and B
The readers can try to find a path and I encourage them to spend some time doing it.
Alas many people have tried and failed. Even the great Mathematician Leonhard Euler tried and failed.
He however had an explanation on why it is not possible to cross all the bridges without revisiting any.
The explanation is so simple and yet so brilliant that most readers will be angry with themselves for not seeing
the solution.
Euler first redraw the map by making the land areas points. See his map below.
What Euler said was very simple. In order to move through a place , you need two bridges.
The first one to enter and the second to leave. Therefore if you do not begin or end at a certain
place, that place will be used only to go through and must have an even amount of bridges.
If the place you start and the place you end up are not the same then these two places must have uneven
number of bridges. The place you start from must have a bridge to leave and the place you end up must have a
bridge to enter. If you end where you start however, that place must have an even number of bridges.
Therefore to cross all bridges , all the areas must have either an even number of bridges or there must be only
two areas with an uneven number of bridges.
When we look at the map of Euler we see all the areas have an uneven number of bridges connected to them.
A has 3 , B has 3 , C has 3 and D has 5. There are therefore 4 areas with an uneven number of bridges.
Hence it is impossible to cross all the bridges only once.
The readers may recognise the image below. It is possible to draw this figure without lifting the pencil and
without revisiting a line already drawn.
The reason is quite simple. There are only two points A and B with an uneven number of lines connected to them.
The rest all have an even number of lines connected to them.