The icosian game is a mathematical game invented in 1856 by Irish mathematician William Rowan Hamilton. It involves finding a Hamiltonian cycle on a dodecahedron, a polygon using edges of the dodecahedron that passes through all its vertices. Hamilton's invention of the game came from his studies of symmetry, and from his invention of the icosian calculus, a mathematical system describing the symmetries of the dodecahedron.
Hamilton sold his work to a game manufacturing company, and it was marketed both in the UK and Europe, but it was too easy to become commercially successful. Only a small number of copies of it are known to survive in museums. Although Hamilton was not the first to study Hamiltonian cycles, his work on this game became the origin of the name of Hamiltonian cycles. Several works of recreational mathematics studied his game. Other puzzles based on Hamiltonian cycles are sold as smartphone apps, and mathematicians continue to study combinatorial games based on Hamiltonian cycles.
Game play
A Hamiltonian cycle on a dodecahedron
Planar view of the same cycle
The game's object is to find a three-dimensional polygon made from the edges of a regular dodecahedron, passing exactly once through each vertex of the dodecahedron. A polygon visiting all vertices in this way is now called a Hamiltonian cycle.) In a two-player version of the game, one player starts by choosing five consecutive vertices along the polygon, and the other player must complete the polygon.
Édouard Lucas describes the shape of any possible solution, in a way that can be remembered by game players. A completed polygon must cut the twelve faces of the dodecahedron into two strips of six pentagons. As this strip passes through each of its four middle pentagons, in turn, it connects through two edges of each pentagon that are not adjacent, making either a shallow left turn or a shallow right turn through the pentagon. In this way, the strip makes two left turns and then two right turns, or vice versa.
One version of the game took the form of a flat wooden board inscribed with a planar graph with the same combinatorial structure as the dodecahedron (a Schlegel diagram), with holes for numbered pegs to be placed at its vertices. The polygon found by game players was indicated by the consecutive numbering of the pegs. Another version was shaped as a "partially flattened dodecahedron", a roughly hemispherical dome with the pentagons of a dodecahedron spread on its curved surface and a handle attached to its flat base. The vertices had fixed pegs. A separate string, with a loop at one end, was wound through these pegs to indicate the polygon.
The game was too easy to play to achieve much popularity, although Hamilton tried to counter this impression by giving an example of an academic colleague who failed to solve it. David Darling suggests that Hamilton may have made it much more difficult for himself than for others, by using his theoretical methods to solve it instead of trial and error.
https://en.wikipedia.org/wiki/Icosian_game
Sir William Rowan Hamilton (4 August 1805 – 2 September 1865) was an Irish mathematician, physicist, and astronomer who made numerous major contributions to algebra, classical mechanics, and optics. His theoretical works and mathematical equations are considered fundamental to modern theoretical physics, particularly his reformulation of Lagrangian mechanics. His research included the analysis of geometrical optics, Fourier analysis, and quaternions, the last of which made him one of the founders of modern linear algebra.
https://en.wikipedia.org/wiki/William_Rowan_Hamilton
A graph having a Hamiltonian cycle, i.e., on which the Icosian game may be played, is said to be a Hamiltonian graph. While the skeletons of all the Platonic solids and Archimedean solids (i.e., the Platonic graphs and Archimedean graphs, respectively) are Hamiltonian, the same is not necessarily true for the skeletons of the Archimedean duals, as shown by Coxeter (1946) and Rosenthal (1946) for the rhombic dodecahedron (Gardner 1984, p. 98).
Wolfram (2022) analyzed the icosian game as a multicomputational process, including through the use of multiway and branchial graphs. In particular, the multiway graph for the icosian game begins as illustrated above.
https://mathworld.wolfram.com/IcosianGame.html
The Original Icosian Game
In 1857 Sir William Rowan Hamilton invented the Icosian game. In a world based on the dodecahedral graph, a traveler must visit 20 cities, without revisiting any of them. Today, when the trip makes a loop through all the vertices of the graph, it is called a Hamiltonian tour (or cycle). When the first and last vertices in a trip are not connected, it is called a Hamiltonian path (or trail). The first image shown is a tour; the second is a path.
Hamiltonian cycles gained popularity in 1880, when P. G. Tait made the conjecture: “Every cubic polyhedron has a Hamiltonian cycle through all its vertices”. Cubic means that three edges meet at every vertex. Without the cubic requirement, there are smaller polyhedra that are not Hamiltonian. The simplest counterexample is the rhombic dodecahedron. Every edge connects one of six valence-four vertices to one of eight valence-three vertices. The six valence-four vertices would need to occupy every other vertex in the length-14 tour. Six items cannot fill seven slots, so this is impossible.
Any noncubic graph can be made cubic by placing a small disk over the exceptions.
The word “polyhedral” implies that the graph must be 3-connected. If a line is drawn to disconnect the map, it must pass through at least three borders. Central Europe is not 3-connected, since a line through Spain will disconnect Portugal. France, the Vatican, and various islands also make the shape of Europe nonpolyhedral.
Tait’s method turns a Hamiltonian cycle on a cubic polyhedral graph into a four-coloring, by the following method.
Alternately color the edges of the Hamiltonian cycle blue and purple. Color the other edges red.
Throw out thin edges, and color the resulting polygon blue.
Throw out dashed edges, and color the resulting polygon(s) red.
Overlay the two colorings to get a four-coloring.
For 66 years, Tait’s conjecture held. In 1946, W. G. Tutte found the first counterexample, now known as Tutte’s graph. Since then, some smaller cubic polyhedral non-Hamiltonian graphs have been found, with the smallest such graph being the Barnette-Bosák-Lederberg graph, found in 1965. Seven years earlier, Lederberg had won the Nobel Prize in Medicine.
https://www.mathematica-journal.com/2010/02/05/the-icosian-game-revisited/#Dalgety
Tutte's fragment
The key to this counter-example is what is now known as Tutte's fragment [...].
If this fragment is part of a larger graph, then any Hamiltonian cycle through the graph must go in or out of the top vertex (and either one of the lower ones). It cannot go in one lower vertex and out the other.
The counterexample
The fragment can then be used to construct the non-Hamiltonian Tutte graph, by putting together three such fragments as shown in the picture.
The "compulsory" edges of the fragments, that must be part of any Hamiltonian path through the fragment, are connected at the central vertex; because any cycle can use only two of these three edges, there can be no Hamiltonian cycle.
The resulting Tutte graph is 3-connected and planar, so by Steinitz' theorem it is the graph of a polyhedron. In total it has 25 faces, 69 edges and 46 vertices. It can be realized geometrically from a tetrahedron (the faces of which correspond to the four large faces in the drawing, three of which are between pairs of fragments and the fourth of which forms the exterior) by multiply truncating three of its vertices.