Why do this problem?
There are many possible routes in the first part of this problem and finding all of them in a systematic way is perhaps too challenging at this level. Asking the pupils to look for several different paths will hopefully help them realise just how many possibilities there are without the need to find an exhaustive list.
Pupils may like to make their own Hamiltonian puzzle, labelling each vertex with the name of a city. They could then write a list of the cities in the order you would have to go to visit each once and only once, and challenge a friend to find the route.