lxv. Icosian Game

Problem (Hamilton, 1857). On the 20 vertices and 30 edges of a dodecahedron (drawn flat as a board), find a tour along edges that visits every vertex exactly once and returns to the start: a Hamiltonian cycle. In Hamilton’s game the first player chooses the first five vertices and the second must complete the tour.

Fact	Value
dodecahedron graph	20 vertices, cubic, planar, girth 5
Hamiltonian cycles	30 (undirected)
Hamilton’s game	every one of the 480 directed 5-vertex starting paths extends to a tour: 360 in exactly 2 ways, 120 in exactly 4 ways
Petersen graph (outer 5-cycle, inner pentagram, 5 spokes)	Hamiltonian paths but no Hamiltonian cycle
Hamiltonian cycle in general	NP-complete, even for cubic planar graphs (Garey, Johnson and Tarjan, 1976)
exact algorithm	bitmask DP $O(2^n{n}^2)$, see Hamiltonian Paths and TSP

Board labels used below: outer pentagon $\mathrm{0..4}$, middle ring $\mathrm{5..14}$ (a 10-cycle), inner pentagon $\mathrm{15..19}$; outer $i$ joins middle $5+2i$, middle $6+2i$ joins inner $15+i$.

vector<vector<int>> dodecahedron() {
    vector<vector<int>> g(20);
    auto e = [&](int a, int b) { g[a].push_back(b); g[b].push_back(a); };
    for (int i = 0; i < 5; i++) { e(i, (i + 1) % 5); e(i, 5 + 2 * i); e(6 + 2 * i, 15 + i); e(15 + i, 15 + (i + 1) % 5); }
    for (int j = 0; j < 10; j++) e(5 + j, 5 + (j + 1) % 10);
    return g;
}
 
ll countHamiltonianCycles(const vector<vector<int>>& g) {   // undirected cycles, n <= 22; O(2^n n^2)
    int n = sz(g); vector<vector<ll>> dp(1 << n, vector<ll>(n, 0)); dp[1][0] = 1;   // paths from vertex 0
    for (int m = 1; m < (1 << n); m += 2) for (int v = 0; v < n; v++) if (dp[m][v])
        for (int u : g[v]) if (!(m >> u & 1)) dp[m | 1 << u][u] += dp[m][v];
    ll s = 0;
    for (int v = 1; v < n; v++) for (int u : g[v]) if (u == 0) s += dp[(1 << n) - 1][v];
    return n >= 3 ? s / 2 : 0;                       // each cycle is counted in both directions
}
 
vector<vector<int>> completeTours(const vector<vector<int>>& g, vector<int> path) {   // Hamilton's game
    int n = sz(g); vector<char> used(n, 0); for (int v : path) used[v] = 1;
    vector<vector<int>> res;
    auto go = [&](auto&& self) -> void {
        if (sz(path) == n) { for (int u : g[path.back()]) if (u == path[0]) res.push_back(path); return; }
        for (int u : g[path.back()]) if (!used[u]) { used[u] = 1; path.push_back(u); self(self); path.pop_back(); used[u] = 0; }
    };
    go(go);
    return res;
}

Proof: the graph is the dodecahedron, and the counts

Structure. Degrees: an outer vertex has 2 pentagon neighbours and 1 middle one; a middle vertex has 2 ring neighbours and 1 outer or inner one; an inner vertex has 2 pentagon neighbours and 1 middle one: cubic, $20\cdot 3/2=30$ edges. The faces of the drawing are the outer pentagon, five pentagons $i,5+2i,6+2i,7+2i,i+1$, five pentagons $6+2i,15+i,16+i,8+2i,7+2i$ (indices mod the ring), and the inner pentagon: 12 pentagonal faces, three at every vertex, which is the dodecahedron.

Counting. dp[m][v] is the number of paths that start at vertex 0, visit exactly the set $m$ and end at $v$: each path is built once, by its last step. A Hamiltonian cycle through 0 corresponds to exactly two such full paths ending at a neighbour of 0 (one per direction), hence the division by 2; every Hamiltonian cycle passes through 0. completeTours enumerates all simple extensions of the given path and keeps those whose last vertex is adjacent to the first. Running them gives 30 cycles for the dodecahedron and 0 for the Petersen graph (whose Hamiltonian paths do exist); over all 480 directed paths of 5 vertices ($20\cdot 3\cdot 2^3$: girth 5 means no such walk repeats a vertex), the completion counts are 2 (360 paths) and 4 (120 paths), so the second player can always win Hamilton’s game. The DP count agrees with plain backtracking on random graphs with up to 12 vertices.

Petersen has no Hamiltonian cycle (by hand). The Petersen graph is cubic with girth 5. Suppose it had a Hamiltonian cycle $0,1,\dots ,9$. The remaining 5 edges form a perfect matching of chords, and a chord between vertices at cyclic distance $d$ would close a cycle of length $d+1$, so every chord has distance 4 or 5. If some chord is a diameter, say $\{0,5\}$: vertex 1 pairs with 6 or 7, and 6 closes the 4-cycle $0,1,6,5$, so $\{1,7\}$; symmetrically $\{9,3\}$. Vertex 2 then pairs with 6 or 8: 6 closes the 4-cycle $1,2,6,7$, and 8 leaves 4 and 6 to be paired at distance 2. If no chord is a diameter, every vertex $v$ pairs with $v\pm 4$; by symmetry $\{0,4\}$; vertex 8 must pair with 2 (its other option, 4, is taken), and then vertex 6, whose options are 0 and 2, has no partner. Both cases are impossible.

Related notes

• Hamiltonian Paths and TSP
• Seven Bridges of Königsberg (Euler tours, the easy cousin)
• Knight’s Tour (Hamiltonian paths on a chessboard)