Hamilton’s icosian game

Solves Hamilton’s 1857 puzzle: travel along the edges of a dodecahedron through all 20 vertices exactly once and return to the start. The same search shows that the Petersen graph has no such cycle.

import matplotlib.pyplot as plt
import numpy as np

from mathematicskit.graph_theory import Graph, dodecahedron_graph, hamiltonian_cycle

A tour of the dodecahedron

g = dodecahedron_graph()
tour = hamiltonian_cycle(g)
print(f"Hamiltonian cycle: {tour}")

radius = {0: 3.0, 1: 2.0, 2: 1.4, 3: 0.7}


def position(v):
    if v < 5:
        return radius[0], 2 * np.pi * v / 5
    if v < 15:
        k = v - 5
        return (radius[1] if k % 2 == 0 else radius[2]), 2 * np.pi * k / 10
    return radius[3], 2 * np.pi * (v - 15) / 5 + 2 * np.pi / 10


pos = np.array([[r * np.sin(t), r * np.cos(t)] for r, t in map(position, range(20))])
fig, ax = plt.subplots(figsize=(6, 6))
for u, v, _ in g.edges():
    ax.plot(*pos[[u, v]].T, color="0.8", lw=1)
cycle = tour + tour[:1]
ax.plot(*pos[cycle].T, color="tab:red", lw=2.5)
ax.plot(*pos.T, "ko")
for v, (x, y) in enumerate(pos):
    ax.annotate(str(v), (x, y), xytext=(4, 4), textcoords="offset points", fontsize=8)
ax.set_aspect("equal")
ax.axis("off")
ax.set_title("The icosian game (Schlegel diagram of the dodecahedron)")

Hamiltonian cycle: [0, 1, 2, 3, 4, 13, 12, 11, 10, 9, 8, 7, 6, 15, 16, 17, 18, 19, 14, 5]

Text(0.5, 1.0, 'The icosian game (Schlegel diagram of the dodecahedron)')

The Petersen graph has no Hamiltonian cycle

petersen = Graph(10)
for i in range(5):
    petersen.add_edge(i, (i + 1) % 5)
    petersen.add_edge(i, i + 5)
    petersen.add_edge(5 + i, 5 + (i + 2) % 5)
print(f"Petersen graph: {hamiltonian_cycle(petersen)}")

Petersen graph: None