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 × n knight's graph is a knight's graph of an m × n chessboard. Its vertices can be represented as the points of the Euclidean plane whose Cartesian coordinates ( x , y ) are integers with 1 ≤ x ≤ m and 1 ≤ y ≤ n (the points at the centers of the chessboard squares), and with two vertices connected by an edge when their Euclidean distance is 5 .

For a m × n knight's graph the total number of vertices is simply n m . For a n × n knight's graph the total number of vertices is simply n 2 and the total number of edges is 4 ( n − 2 ) ( n − 1 ) .

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

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