# 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 $m\times n$ knight's graph is a knight's graph of an $m\times n$ chessboard. Its vertices can be represented as the points of the Euclidean plane whose Cartesian coordinates $(x,y)$ are integers with $1\leq x\leq m$ and $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 ${\sqrt {5}}$ .

Knight's graph $8\times 8$ knight's graph
Vertices$mn$ Edges$4mn-6(m+n)+8$ (if $n\geq 2$ and $m\geq 2$ )
Girth4 (if $n\geq 3$ and $m\geq 5$ )
Propertiesbipartite
Table of graphs and parameters

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

A Hamiltonian cycle on the knight's graph is a (closed) knight's tour. 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.

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 $4\times 4$ knight's graph is the same as the four-dimensional hypercube graph.