In graph theory and recreational mathematics, the Hanoi graphs are undirected graphs whose vertices represent the possible states of the Tower of Hanoi puzzle, and whose edges represent allowable moves between pairs of states.
Construction
The puzzle consists of a set of disks of different sizes, placed in increasing order of size on a fixed set of towers. The Hanoi graph for a puzzle with n {\displaystyle n} disks on k {\displaystyle k} towers is denoted H k n {\displaystyle H_{k}^{n}} . Each state of the puzzle is determined by the choice of one tower for each disk, so the graph has k n {\displaystyle k^{n}} vertices. In the moves of the puzzle, the smallest disk on one tower is moved either to an unoccupied tower or to a tower whose smallest disk is larger. If there are u {\displaystyle u} unoccupied towers, the number of allowable moves is
( k 2 ) − ( u 2 ) , {\displaystyle {\binom {k}{2}}-{\binom {u}{2}},}
which ranges from a maximum of ( k 2 ) {\displaystyle {\tbinom {k}{2}}}
(when u {\displaystyle u} is zero or one and ( u 2 ) {\displaystyle {\tbinom {u}{2}}} is zero) to k − 1 {\displaystyle k-1} (when all disks are on one tower and u {\displaystyle u} is k − 1 {\displaystyle k-1} ). Therefore, the degrees of the vertices in the Hanoi graph range from a maximum of ( k 2 ) {\displaystyle {\tbinom {k}{2}}} to a minimum of k − 1 {\displaystyle k-1} . The total number of edges is
1 2 ( k 2 ) ( k n − ( k − 2 ) n ) . {\displaystyle {\frac {1}{2}}{\binom {k}{2}}{\bigl (}k^{n}-(k-2)^{n}{\bigr )}.}
For k = 0 {\displaystyle k=0} (no disks) there is only one state of the puzzle and one vertex of the graph. For k > 0 {\displaystyle k>0} , the Hanoi graph H k n {\displaystyle H_{k}^{n}} can be decomposed into k {\displaystyle k} copies of the smaller Hanoi graph H k n − 1 {\displaystyle H_{k}^{n-1}} , one for each placement of the largest disk. These copies are connected to each other only at states where the largest disk is free to move: it is the only disk in its tower, and some other tower is unoccupied.
General properties
Every Hanoi graph contains a Hamiltonian cycle. The Hanoi graph H k 1 {\displaystyle H_{k}^{1}} is a complete graph on k {\displaystyle k} vertices. Because they contain complete graphs, all larger Hanoi graphs H k n {\displaystyle H_{k}^{n}} require at least k {\displaystyle k} colors in any graph coloring. They may be colored with exactly k {\displaystyle k} colors by summing the indexes of the towers containing each disk, and using the sum modulo k {\displaystyle k} as the color.
… excerpt ends here. Continue reading the full article.
