Hanoi graph explained

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

disks on

towers is denoted

	n
H
	k

. Each state of the puzzle is determined by the choice of one tower for each disk, so the graph has

kⁿ

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

unoccupied towers, the number of allowable moves is

\binom{k}{2}-\binom{u}{2},

which ranges from a maximum of

\tbinom{k}{2}

(when

is zero or one and

\tbinom{u}{2}

is zero)to

k-1

(when all disks are on one tower and

k-1

). Therefore, the degrees of the vertices in the Hanoi graph range from a maximum of

\tbinom{k}{2}

to a minimum of

k-1

.The total number of edges is

	1
	2

\binom{k}{2}l(k^n-(k-2)^nr).

For

k=0

(no disks) there is only one state of the puzzle and one vertex of the graph.For

k>0

, the Hanoi graph

	n
H
	k

can be decomposed into

copies of the smaller Hanoi graph

	n-1
H
	k

, 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

lang=cy|thumb|300px|

	3
H
	3

with 12 edges deleted to yield a Hamiltonian cycleEvery Hanoi graph contains a Hamiltonian cycle.

The Hanoi graph

	1
H
	k

is a complete graph on

vertices. Because they contain complete graphs, all larger Hanoi graphs

	n
H
	k

require at least

colors in any graph coloring. They may be colored with exactly

colors by summing the indexes of the towers containing each disk, and using the sum modulo

as the color.

Three towers

A particular case of the Hanoi graphs that has been well studied since the work of is the case of the three-tower Hanoi graphs,

	n
H
	3

. These graphs have vertices and edges .^[1] They are penny graphs (the contact graphs of non-overlapping unit disks in the plane), with an arrangement of disks that resembles the Sierpinski triangle. One way of constructing this arrangement is to arrange the numbers of Pascal's triangle on the points of a hexagonal lattice, with unit spacing, and place a unit disk on each point whose number is odd.The diameter of these graphs, and the length of the solution to the standard form of the Tower of Hanoi puzzle (in which the disks all start on one tower and must all move to one other tower) is

2ⁿ-1

More than three towers

For

k>3

, the structure of the Hanoi graphs is not as well understood, and the diameter of these graphs is unknown.When

k>4

and

n>0

or when

k=4

and

n>2

, these graphs are nonplanar.

Notes and References

Web site: Hanoi Graph.