Copyright © University of Cambridge. All rights reserved.
Leonhard Euler wrote the first mathematical paper on graph theory in 1736 in which he discussed whether or not it was possible to stroll around Konigsberg (now called Kaliningrad) crossing each of its seven bridges across the river Pregel exactly once.
Here are two sketch maps. Try for yourself. What do you think?
Now experiment with different numbers of islands and bridges.
Satisfy yourself that with some configurations it is possible to trace a continuous path:
which crosses every bridge once only and returns to the starting point (a bridge traversing circuit),
which crosses every bridge once only but does not return to the starting point (a bridge traversing path),
which passes through each of the islands exactly once and returns to its starting point (a Hamiltonian circuit),
and with other configurations it is not possible to do so.
Draw 3 diagrams with 8 bridges, one in which a bridge traversing circuit is possible, one in which a bridge traversing path is possible, and one in which neither are possible.