Hamilton's Puzzle

In 1859, the Irish mathematician Sir William Rowan Hamilton devised a puzzle with a regular dodecahedron made of wood. Here is a dodecahedron:

He labelled each of the vertices with the name of an important city. The challenge was to find a route along the edges of the dodecahedron which visited every city exactly once and returned to the start.

Here is a graph which represents the dodecahedron. Can you see how each of the 20 vertices, 30 edges and 12 pentagonal faces is represented in the graph?

I start my journey in Rio de Janeiro and visit all the cities as Hamilton described, passing through Canberra before Madrid, and then returning to Rio. What route could I have taken?

Can you find any other ways of making this journey?

Here is a simpler network of countries:

How many different ways are there of visiting each of these countries once and only once, beginning and ending at Australia?