# 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}$)
Girth4 (if ${\displaystyle n\geq 3}$ and ${\displaystyle m\geq 5}$)
Propertiesbipartite
Table of graphs and parameters

For an ${\displaystyle m\times n}$ knight's graph, the number of vertices is ${\displaystyle nm}$. If ${\displaystyle m>1}$ and ${\displaystyle n>1}$ then the number of edges is ${\displaystyle 4mn-6(m+n)+8}$ (otherwise there are no edges). For an ${\displaystyle n\times n}$ knight's graph, these simplify so that 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 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]