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.
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?
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.
Thank you for all your solutions. I think it is quite difficult
to explain the solution to this problem but many of you noticed the
pattern of the nodes in the diagram and the importance of the fact
that there are four nodes on the diagram, each of which has an odd
number of routes from it.
The model of the town, where each island and each side of the
river has an odd number of bridges leading to/from it, was included
so that you could relate it to the diagrams in the hints. To be
able to move from each of the four regions you must have two areas
with an even number of bridges so that you can arrive and leave.
Solutions received from Andrei of School 205 Bucharest, Alex and
Joanna of Woodfall Junior School, Katherine, Phoebe and Katharine
of The Mount School and Gowri, Hannah and Sophie of Caistor Grammar
School used this idea.
The hints were there to help you to identify the importance of
the number of odd nodes. It is worth going back to these and try to
generalise your findings from this problem to other similar
Andrei observed that the city is symmetrical in respect to a
The journey is impossible.
Suppose the starting point of the walk is on a side of the river
(it could be north or south, as specified the city is symmetrical);
there are three bridges. The people must first go on the first
bridge, return on the second, and then go away by the third, so
they cannot come back! There must be an even number of bridges on
each part so, that they can return home.
After solving the problem this way, I discovered that this is a
famous problem of the history of mathematics, being at the basis of
topology of networks, first developed by Euler in 1735. He
constructed a diagram (essentially the same as yours), and
associated the land with the vertices, and the bridges with the
possible ways of connecting the vertices - arcs.
Using the reciprocal of Euler's theorem: "if a network has two or
less odd vertices, it has at least an Euler path", that says "if a
network has two or less odd vertices, it has at least an Euler
path", it is easy to see that the proposed problem does not admit
an Euler path (i.e. a continuous path that passes through every arc
once and only once).