Video 2, chapter 23

The Icosian Tour and Hamiltonian Cycles

How the Icosian game asks for a Hamiltonian cycle of the dodecahedral graph, a route that visits every vertex once before returning, how to build one, and why Euler's count of odd vertices does not decide it.

  • Video 2, chapter 23
  • Turn a route into a graph

Take the twenty corners of a dodecahedron and the thirty edges between them. Can you walk along the edges, visit every corner exactly once, and end where you began? The question sounds like the bridge puzzle of Königsberg, but its rule is about vertices instead of edges, and that small change gives a very different problem. This page builds one complete tour, shows why a pentagon closed too early is a dead end, and explains why counting odd degrees settles nothing here.

Key terms

Icosian game

Definition The Icosian game is a puzzle invented by the mathematician William Rowan Hamilton in 1857, with a name that comes from the Greek word for twenty. It is played on the dodecahedral graph, whose 2020 vertices and 3030 edges are the corners and edges of a regular dodecahedron. The player must find a route that moves only along edges, visits each of the 2020 vertices exactly once, and then returns along one more edge to the starting vertex. The route may start at any vertex and may leave edges unused, but it may not jump between two vertices that no edge joins, and the start is the only vertex it reaches twice. The answer is that such routes exist. A computer search through all possibilities finds exactly 3030 of them, counting two routes as the same when they use the same 2020 edges, so that the starting vertex and the direction of travel do not matter.

In plain words Visit every corner of the dodecahedron once, walking only along its edges, and come back to where you started. Unlike the bridge puzzle, you do not have to use every edge.

Example Draw the graph with an outer ring of ten vertices u0,u1,…,u9u_0, u_1, \ldots, u_9 and ten inner vertices v0,v1,…,v9v_0, v_1, \ldots, v_9. Every outer vertex uiu_i is joined to its two neighbors on the ring and, by a spoke, to the inner vertex viv_i. Every inner vertex viv_i is joined to vi+2v_{i+2} and vi−2v_{i-2}, with labels counted around so that after 99 comes 00 again. One tour is

u0,u1,u2,u3,u4,u5,u6,u7,v7,v5,v3,v1,v9,u9,u8,v8,v6,v4,v2,v0,u0.\begin{gathered} u_0, u_1, u_2, u_3, u_4, u_5, u_6, \\[0.4em] u_7, v_7, v_5, v_3, v_1, v_9, u_9, \\[0.4em] u_8, v_8, v_6, v_4, v_2, v_0, u_0. \end{gathered}

It runs around the outer ring from u0u_0 to u7u_7, steps in to v7v_7 and moves through the inner vertices with odd labels to v9v_9, steps out to u9u_9 and along the ring to u8u_8, steps in to v8v_8, moves through the inner vertices with even labels to v0v_0, and returns to u0u_0 along a spoke. Every two consecutive vertices are joined by an edge, including v1v_1 and v9v_9, since 1−21 - 2 counts back around to 99. The 2020 vertices before the return are all different, so this is a solution, and it uses 2020 of the 3030 edges.

Hamiltonian cycle

Definition Let a graph have n≥3n \ge 3 vertices. A Hamiltonian cycle is a list w1,w2,…,wnw_1, w_2, \ldots, w_n that contains every vertex exactly once, such that wiw_i and wi+1w_{i+1} are joined by an edge for i=1,…,n−1i = 1, \ldots, n - 1 and wnw_n is joined by an edge to w1w_1. As a route, it visits every vertex once and returns to the start, which is the only vertex reached twice. The same cycle can be listed from any starting vertex and in either direction. It uses nn different edges, and every vertex meets exactly two of them, one for arriving and one for leaving. That condition is necessary but not sufficient, because a set of edges with exactly two at every vertex can split into several separate cycles. A graph that has a Hamiltonian cycle is called Hamiltonian. No simple rule like Euler’s count of odd vertices is known that decides for every graph whether it is Hamiltonian, and no efficient method that works for all graphs is known. Necessary conditions, such as two chosen edges at every vertex, together with careful search are the usual tools.

In plain words Visit every dot exactly once along the lines and return to where you started. At every dot the route uses exactly two lines, one in and one out.

Example Every vertex of the dodecahedral graph has degree 33, so a Hamiltonian cycle uses two of the three edges at each vertex and leaves exactly one unused. In the tour above the 1010 unused edges are u0u9u_0u_9, u7u8u_7u_8, v0v8v_0v_8, v7v9v_7v_9 and the six spokes from u1v1u_1v_1 to u6v6u_6v_6, and each vertex is an end of exactly one of them. The same condition shows how a search can go wrong. The five vertices u9,u0,u1,v1,v9u_9, u_0, u_1, v_1, v_9 form a pentagon, a cycle of five edges. If a partial tour includes all five of its edges, each of those five vertices already has its two tour edges, so no tour edge can join them to the other 1515 vertices, and the chosen edges can never become one cycle through all 2020. A search should reject that choice as soon as it closes the pentagon.

Dodecahedral graph

Definition A regular dodecahedron is a solid with 1212 faces, each a regular pentagon, with three faces meeting at each of its 2020 corners. The dodecahedral graph has the 2020 corners as vertices and the 3030 edges of the solid as edges. Every vertex has degree 33, and the degrees add up to 6060, twice the number of edges. In the ring drawing used on this page the vertices are u0,…,u9u_0, \ldots, u_9 and v0,…,v9v_0, \ldots, v_9, labels are counted modulo 1010, which means that after 99 comes 00 again, and the edges are

uiui+1,uivi,vivi+2\begin{gathered} u_i u_{i+1}, \qquad u_i v_i, \\[0.4em] v_i v_{i+2} \end{gathered}

for i=0,1,…,9i = 0, 1, \ldots, 9, ten edges of each kind, forming the outer ring, the spokes and the inner edges. The inner edges join the even labels in one five-cycle v0,v2,v4,v6,v8v_0, v_2, v_4, v_6, v_8 and the odd labels in another. In the drawing the two inner five-cycles cross each other, but a crossing of two drawn lines is not a vertex, and a route may only turn at a vertex. The graph can also be drawn with no crossings at all, for example as the view into the solid through one of its faces. Its shortest cycles have five edges, and there are exactly 1212 of them, the boundaries of the 1212 faces.

In plain words Twenty dots, each joined to three others, in the pattern of the corners and edges of a dodecahedron. The ring drawing puts ten dots on an outer circle and ten inside, so that every vertex has a short name and a route can be checked step by step.

Example The vertex u3u_3 is joined to u2u_2, u4u_4 and v3v_3, and the vertex v9v_9 is joined to u9u_9, v7v_7 and v1v_1, since 9+2=119 + 2 = 11 counts around to 11. The edges can be counted in two ways. There are 2020 vertices with 33 edge ends each, 6060 ends in all, so there are 3030 edges. There are also 1212 faces with 55 sides each, 6060 sides in all, and each edge borders exactly two faces, which again gives 3030. In the ring drawing the faces are the two inner five-cycles and the ten pentagons ui−1,ui,ui+1,vi+1,vi−1u_{i-1}, u_i, u_{i+1}, v_{i+1}, v_{i-1}, one for each ii.

Graph traversal

Definition A graph traversal is a walk that moves through a graph along its edges in order to cover it, following a rule that says what must be covered and what may be repeated. An Eulerian path must use every edge exactly once and may pass through vertices again. A Hamiltonian cycle must visit every vertex exactly once before returning to its start and may leave edges unused. The two rules ask different questions with different answers. Euler’s theorem decides the first by counting odd vertices and checking that the graph is connected, while for the second no such count works. In computer science the term also names systematic procedures, such as depth-first search and breadth-first search, that visit every vertex that can be reached from a starting vertex.

In plain words Before searching for a route, read the rule. Covering every line and covering every dot are different goals, and a fact about one of them does not answer the other.

Example Small graphs show that neither question answers the other. In the complete graph on the four vertices 1,2,3,41, 2, 3, 4, where every two vertices are joined by an edge, each vertex has degree 33. Its four odd vertices rule out an Eulerian path, yet 1,2,3,4,11, 2, 3, 4, 1 is a Hamiltonian cycle. The bowtie is made of two triangles, 1,2,31, 2, 3 and 3,4,53, 4, 5, that share the vertex 33. Its degrees are 2,2,4,2,22, 2, 4, 2, 2, all even, and it is connected, so 1,2,3,4,5,3,11, 2, 3, 4, 5, 3, 1 is an Eulerian circuit. But it has no Hamiltonian cycle, because every route from the first triangle to the second passes through 33, so a cycle through 11 and 44 would reach 33 on the way out and again on the way back. The dodecahedral graph has 2020 odd vertices, so no walk uses each of its 3030 edges exactly once, and still it has a Hamiltonian cycle.

Check yourself

  1. The eight corners of a cube can be named by the strings 000,001,…,111000, 001, \ldots, 111 of three binary digits, which are their coordinates when the cube has side 11, one corner at the origin and its edges along the coordinate axes. Two corners are joined by an edge of the cube exactly when their names differ in one digit. Find a Hamiltonian cycle of this cube graph. Is there also a walk that uses each of its 1212 edges exactly once?
Show the answer

One Hamiltonian cycle is

000,001,011,010,110,111,101,100,000.\begin{gathered} 000, 001, 011, \\[0.4em] 010, 110, 111, \\[0.4em] 101, 100, 000. \end{gathered}

Each step changes exactly one digit, so every two consecutive corners are joined by an edge, and the eight names before the return are all different. The cycle uses 88 of the 1212 edges. Every corner has degree 33, one edge for each digit that can be changed, so all eight corners are odd vertices. That is more than two, so by Euler’s theorem no walk uses each edge exactly once. Like the dodecahedral graph, the cube graph has a Hamiltonian cycle but no Eulerian path.

  1. Add a new vertex ww to the dodecahedral graph, joined by a single edge to u0u_0. Does the new graph of 2121 vertices have a Hamiltonian cycle? What changes if ww is joined to both u0u_0 and u1u_1?
Show the answer

With one edge at ww there is no Hamiltonian cycle. A Hamiltonian cycle needs two edges at every vertex, one to arrive and one to leave, and ww has only one. The reason is not that the degree of ww is odd. Every vertex of the dodecahedral graph has odd degree as well, and that graph has a Hamiltonian cycle.

With edges to both u0u_0 and u1u_1 there is one. Any Hamiltonian cycle must use both edges at ww, so it contains the steps u0,w,u1u_0, w, u_1. The tour found above begins with the edge from u0u_0 to u1u_1, so replace that step by the detour through ww. The route that starts u0,w,u1,u2u_0, w, u_1, u_2 and then continues exactly as before, through v0v_0 and back to u0u_0, visits all 2121 vertices once and returns to its start.

  1. Change the number 1010 to 55 in the ring drawing. Take outer vertices u0,…,u4u_0, \ldots, u_4 in a ring, spokes uiviu_iv_i, and inner edges vivi+2v_iv_{i+2}, with labels now counted modulo 55. This is the Petersen graph, with 1010 vertices and 1515 edges, and like the dodecahedral graph it has degree 33 at every vertex. Show that it has no Hamiltonian cycle.
Show the answer

The spokes are the only edges between outer and inner vertices. A Hamiltonian cycle visits both kinds, and to return to its start it must cross between them an even number of times, so it uses either 22 or 44 of the 55 spokes. The inner edges form the five-cycle v0,v2,v4,v1,v3v_0, v_2, v_4, v_1, v_3. A path through all five vertices of a five-cycle uses four of its edges and leaves out the one that joins the path’s two ends.

Suppose the cycle uses 22 spokes. Then it consists of a path through all five outer vertices, a spoke, a path through all five inner vertices, and the other spoke. The outer path ends at two neighbors on the ring, say uau_a and ua+1u_{a+1}, so the spokes lead to vav_a and va+1v_{a+1}, and the inner path runs between those two. Its ends would have to be joined by an inner edge, but an inner edge joins viv_i only to vi+2v_{i+2} and vi−2v_{i-2}, never to vi+1v_{i+1}.

Suppose the cycle uses 44 spokes. Turning the labels around the ring maps the graph onto itself, so we may take the unused spoke to be u0v0u_0v_0. Then u0u_0 must use both of its ring edges, u0u1u_0u_1 and u0u4u_0u_4. The vertex u1u_1 now has its two cycle edges, u0u1u_0u_1 and its spoke, so u1u2u_1u_2 is unused, and in the same way u3u4u_3u_4 is unused. On the inside, v0v_0 must use v0v2v_0v_2 and v0v3v_0v_3. Then v2v_2 has v0v2v_0v_2 and its spoke, so v2v4v_2v_4 is unused, and v3v_3 has v0v3v_0v_3 and its spoke, so v1v3v_1v_3 is unused. The only edges left for v4v_4 are its spoke and v1v4v_1v_4. The chosen edges therefore include the closed loop u0,u1,v1,v4,u4,u0u_0, u_1, v_1, v_4, u_4, u_0 through only five vertices, so they cannot form a single cycle through all ten.

Either way a Hamiltonian cycle is impossible, and a computer search confirms that the Petersen graph has none, while the dodecahedral graph has 3030. Every vertex has degree 33 in both graphs, so the degrees alone cannot tell the two apart.

How this lesson connects