You may also like

problem icon

Icosian Game

This problem is about investigating whether it is possible to start at one vertex of a platonic solid and visit every other vertex once only returning to the vertex you started at.

problem icon

Travelling Salesman

A Hamiltonian circuit is a continuous path in a graph that passes through each of the vertices exactly once and returns to the start. How many Hamiltonian circuits can you find in these graphs?

problem icon

Tourism

If you can copy a network without lifting your pen off the paper and without drawing any line twice, then it is traversable. Decide which of these diagrams are traversable.

Königsberg

Stage: 3 Challenge Level: Challenge Level:2 Challenge Level:2

Legend has it that the 'gentlefolk' of Königsberg would spend their Sunday afternoons walking around the town. It is believed they were attempting to cross each of the seven bridges, that join the north and south of the river to the two islands, once and once only without retracing their steps.

You might find it easier to study a more diagrammatic representation below (green dots represent the land to the north and south of the river and blue dots the two islands):

Can you succeed where the people of Königsberg failed, and solve the problem of the seven bridges? If not, can you explain why not? If you can, explain how you know that you have all the solutions?