The knight graph is a graph on vertices in which each vertex represents a square in an chessboard, and each edge corresponds to a legal move by a knight (which may only make moves which simultaneously shift one square along one axis and two along the other). It is therefore a leaper graph.
The knight graph consists of an 8cycle together with an (unreachable from all of the other squares) isolated central vertex.
The number of edges in the knight graph is (8 times the triangular numbers), so for , 2, ..., the first few values are 0, 0, 8, 24, 48, 80, 120, ... (OEIS A033996).
Knight graphs are bipartite and therefore are perfect.
The following table summarizes some named graph complements of knight graphs.
knight graph  queen graph 
knight graph  queen graph 
The knight graph is implemented in the Wolfram Language as KnightTourGraph[m, n], and precomputed properties are available in using GraphData["Knight", m, n].
Closed formulas for the numbers of graph cycles of the knight graph are given by for odd and
(1)

(E. Weisstein, Nov. 16, 2014).
A knight's path is a sequence of moves by a knight such that each square of the board is visited exactly once. It is therefore a Hamiltonian path on the corresponding knight graph. Conrad et al. (1994) shows that a knight's path exists on an board iff .
The above figures show six knight's paths on an chessboard, all but the first of which are reentrant. The final path has the additional property that it is a semimagic square with row and column sums of 260 and main diagonal sums of 348 and 168 (Steinhaus 1999, p. 30).
If the final position of such a path is a knight's move away from the initial position of the knight, the path is called reentrant or closed and corresponds to a Hamiltonian cycle on the underlying knight graph. Conrad et al. (1994) shows that a knight's tour exists on an board iff and is even.
Backtracking algorithms (in which the knight is allowed to move as far as possible until it comes to a blind alley, at which point it backs up some number of steps and then tries a different path) can be used to find knight's tours, but such methods can be very slow. Warnsdorff (1823) proposed an algorithm that finds a path without any backtracking by computing ratings for "successor" steps at each position. Here, successors of a position are those squares that have not yet been visited and can be reached by a single move from the given position. The rating is highest for the successor whose number of successors is least. In this way, squares tending to be isolated are visited first and therefore prevented from being isolated (Roth). The time needed for this algorithm grows roughly linearly with the number of squares of the chessboard, but unfortunately computer implementation show that this algorithm runs into blind alleys for chessboards bigger than , despite the fact that it works well on smaller boards (Roth).
Conrad et al. (1994) discovered another linear time algorithm and proved that it solves the Hamiltonian path problem for all . The Conrad et al. algorithm works by decomposition of the chessboard into smaller chessboards (not necessarily square) for which explicit solutions are known. This algorithm is rather complicated because it has to deal with many special cases, but has been implemented in the Wolfram Language by A. Roth. Example tours are illustrated above for boards with to 8.
The numbers of (undirected) closed knight's tours (i.e., Hamiltonian cycles) on a chessboard for , 2, ... are 0, 0, 9862, 13267364410532, ... (OEIS A001230; Ball and Coxeter 1987; Wegener 2000, p. 369; Elkies and Stanley 2003). There are no closed tours for boards with odd. Kraitchik (1942, pp. 264265) also notes that there are 1728 total paths on the square, 8 of which are symmetric, and there are five doubly symmetric paths on the square. The number of cycles covering the directed knight's graph for an chessboard was computed by Wegener and Löbbing (1996) as . They also computed the number of undirected tours, obtaining an incorrect answer (which is not divisible by 4 as it must be). The correct value of appears in Wegener's subsequent book (Wegener 2000), and also agrees with unpublished calculations of B. D. McKay.
The longest "uncrossed" knight's tours on an board for , 4, ... are 2, 5, 10, 17, 24, 35, ... (OEIS A003192).
The following table extends and corrects some additional results given by Kraitchik (1942, pp. 264265). Here, DHP means geometrically distinct Hamiltonian paths, DSHP means geometrically distinct symmetric paths, HP means total (directed) Hamiltonian paths, DHC means geometrically distinct Hamiltonian cycles, and HC means total (directed) Hamiltonian cycles.
size  DHP  DSHP  HP  DHC  HC 
Sloane  A118067  A158074  
0  0  0  0  0  
0  0  0  0  0  
3  16  0  0  
0  0  0  0  
0  0  0  0  
14  2  104  0  0  
104  792  0  0  
146  16  1120  0  0  
773  6096  8  32  
2698  58  21344  0  0  
14350  114496  28  352  
32296  257728  0  0  
3072  
0  0  
30848 
Amazingly, the number of Hamiltonian cycles on the knight graph is given by the 21storder linear recurrence equation
(2)

with corresponding closedform generating function
(3)
 
(4)

where
(5)
 
(6)

This result was obtained independently by D. E. Knuth and N. D. Elkies in April 1994, both using the socalled transfermatrix method (Stanley 1999, Ch. 4.7; Elkies and Stanley 2003).
The numbers of possible (directed) closed tours on a board for , 4, ... are 16, 0, 164, 1488, 12756, 62176, 379376, 2426224, ... (OEIS A123935; Kraitchik 1942, p. 263). Like the case, this sequence is known to be given by a linear recurrence relation with constant coefficients, although it appears this recurrence has not yet been explicitly computed.
The knight graph is Hamiltonlaceable iff , , and at least one of , is even (Dupuis and Wagon 2014).