Reference articles on history, science, culture and more
Surprise meSurprise meSubscribe
Encyclopedia

Knight's graph

Mathematical graph relating to chess

Wikipedia contributorsAdapted for Fathomly · View authors
1 min read
Source updated April 5, 2026
Image credit is listed at the end of this article.

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

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 (each color of squares can be used as one of two independent sets, and knight moves always change square color) and only bipartite graphs with an even number of vertices can have Hamiltonian cycles. Most 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.

Watch videos about Knight's graphExplainers and documentaries on YouTube (opens in a new tab)

Sources and credits

This article is adapted from the Wikipedia article “Knight's graph”, written by its contributors and licensed under CC BY-SA 4.0. Fathomly has changed the layout, removed citation markers, navigation and maintenance notices, and adjusted punctuation. This adapted version is shared under the same license. For references, see the original article.

Images, from Wikimedia Commons:

Fathomly is not affiliated with or endorsed by the Wikimedia Foundation. Spotted a problem? Tell us.

Continue exploring

Related topics

King's graph

In graph theory, a king's graph is a graph that represents all legal moves of the king chess piece on a chessboard where each vertex represents a square on a chessboard and each edge is a legal move. More specifically, an n × m {\displaystyle n\times m} king's graph is a king's graph of an n × m {\displaystyle n\times m} chessboard.

Queen's graph

In mathematics, a queen's graph is an undirected graph that represents all legal moves of the queen, a chess piece, on a chessboard. In the graph, each vertex represents a square on a chessboard, and each edge is a legal move the queen can make; that is, a horizontal, vertical or diagonal move by any number of squares.

Rook's graph

In graph theory, a rook's graph is an undirected graph that represents all legal moves of the rook chess piece on a chessboard. Each vertex of a rook's graph represents a square on a chessboard, and there is an edge between any two squares sharing a row or column (file), the squares that a rook can move between.