In how many distinct ways can six islands be joined by bridges so that each island can be reached from every other island...
The graph represents a salesman’s area of activity with the
shops that the salesman must visit each day. What route around the
shops has the minimum total distance?
The reader is invited to investigate changes (or permutations) in the ringing of church bells, illustrated by braid diagrams showing the order in which the bells are rung.
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
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.