# Knight's graph

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

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}}}$.

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

A Hamiltonian cycle on the knight's graph is a 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]