Knight's graph

Knight's graph
8x8 Knight's graph
Vertices	nm
Edges	4mn-6(m+n)+8
Girth	4 (if n≥3, m≥ 5)

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 where each vertex represents a square on a chessboard and each edge is a legal move. More specifically, an $n \times m$ knight's tour graph is a knight's tour graph of an $n \times m$ chessboard.

For a $n \times m$ knight's tour graph the total number of vertices is simply nm.

For a $n \times n$ knight's tour graph the total number of vertices is simply n² and the total number of edges is 4(n–2)(n–1). Additionally, the number of edges for various n is identified as  A033996 in the On-Line Encyclopedia of Integer Sequences.

A Hamiltonian path on the knight's tour graph is a knight's tour.

The following Knight's graph shows the number of possible moves that can be made from each position on an 8×8 chessboard.

See also

• King's graph
• Rook's graph
• Schwenk's theorem