Knight's graph

In graph theory, a knight's graph, or a knight's tour graph, is a graph that represents all legal moves of the knight chess piece on a chessboard. Each vertex of this graph represents a square of the chessboard, and each edge connects two squares that are a knight's move apart from each other. More specifically, an ${\displaystyle m\times n}$ knight's graph is a knight's graph of an ${\displaystyle m\times n}$ chessboard.[1] Its vertices can be represented as the points of the Euclidean plane whose Cartesian coordinates ${\displaystyle (x,y)}$ are integers with ${\displaystyle 1\leq x\leq m}$ and ${\displaystyle 1\leq y\leq n}$ (the points at the centers of the chessboard squares), and with two vertices connected by an edge when their Euclidean distance is ${\displaystyle {\sqrt {5}}}$.

Knight's graph
${\displaystyle 8\times 8}$ knight's graph
Vertices	${\displaystyle mn}$
Edges	${\displaystyle 4mn-6(m+n)+8}$ (if ${\displaystyle n\geq 2}$ and ${\displaystyle m\geq 2}$)
Girth	4 (if ${\displaystyle n\geq 3}$ and ${\displaystyle m\geq 5}$)
Properties	bipartite
Table of graphs and parameters

For an ${\displaystyle m\times n}$ knight's graph, the number of vertices is ${\displaystyle nm}$. For an ${\displaystyle n\times n}$ knight's graph, the number of vertices is ${\displaystyle n^{2}}$ and the number of edges is ${\displaystyle 4(n-2)(n-1)}$.[2]

A Hamiltonian cycle on the knight's graph is a (closed) knight's tour.[1] A chessboard with an odd number of squares has no tour, because the knight's graph is a bipartite graph and only the bipartite graphs with an even number of vertices can have Hamiltonian cycles. All but finitely many chessboards with an even number of squares have a knight's tour; Schwenk's theorem provides an exact listing of which ones do and which do not.[3]

When it is modified to have toroidal boundary conditions (meaning that a knight is not blocked by the edge of the board, but instead continues onto the opposite edge) the ${\displaystyle 4\times 4}$ knight's graph is the same as the four-dimensional hypercube graph.[3]

See also

• King's graph
• Rook's graph

References

1. Averbach, Bonnie; Chein, Orin (1980), Problem Solving Through Recreational Mathematics, Dover, p. 195, ISBN 9780486131740.
2. Sloane, N. J. A. (ed.). "Sequence A033996". The On-Line Encyclopedia of Integer Sequences. OEIS Foundation.
3. Watkins, John J. (2004), Across the Board: The Mathematics of Chessboard Problems. Paradoxes, perplexities, and mathematical conundrums for the serious head scratcher, Princeton University Press, pp. 44, 68, ISBN 978-0-691-15498-5.

External links

• Weisstein, Eric W. "Knight Graph". MathWorld.