Fact-checked by Grok 2 weeks ago

Knight's graph

In , the knight's (also known as the knight's tour ) is defined on an m × n as a with mn vertices, each representing a square of the board, and edges connecting pairs of vertices that are separated by a single 's move in chess (an L-shaped trajectory of two squares in one direction and one perpendicular, or vice versa). This is a specific instance of a (1,2)-leaper and a -√5 , capturing all legal moves of the piece without regard to other pieces on the board. The is fundamentally bipartite, with vertices partitioned into two sets corresponding to the squares of the , as a knight always moves from one color to the other; this bipartition implies that the graph is perfect, meaning its chromatic number equals its number for every . For an n × n square board, the number of edges is given by 4(n-2)(n-1), yielding 168 edges on the standard 8×8 board. The graph's structure underpins the classical problem, where an open tour corresponds to a visiting each exactly once, and a closed tour corresponds to a returning to the starting . Existence results for Hamiltonian paths and cycles in the knight's graph have been thoroughly characterized. On an n × n board, a Hamiltonian path exists if and only if n ≥ 5. For closed tours on rectangular m × n boards with m ≤ n, they exist unless m and n are both odd, or m = 1, 2, or 4, or (m = 3 and n = 4, 6, or 8). These findings resolve long-standing questions in combinatorial and have applications in puzzle-solving algorithms and analysis.

Definition

Formal definition

The knight's graph of an m \times n chessboard is an undirected simple whose vertex set consists of the m n squares of the board, each labeled by coordinates (i, j) where $1 \leq i \leq m and $1 \leq j \leq n. Two distinct vertices are adjacent via an edge if and only if a chess can legally move between the corresponding squares in one step, which requires a change in coordinates of (\pm 1, \pm 2) or (\pm 2, \pm 1) while remaining within the board boundaries. The contains no self-loops or multiple edges. This adjacency structure is based on the L-shaped , which connects squares separated by a of \sqrt{5}. The is bipartite, with the bipartition induced by the standard black-and-white coloring of the .

Variants on different boards

The knight's graph on a finite m \times n board consists of mn vertices arranged in a rectangular , with edges connecting positions that differ by a knight's move, provided the destination remains within the board boundaries. For small dimensions, the graph exhibits limited connectivity due to boundary constraints. On a $1 \times n board, no legal moves are possible, resulting in n isolated vertices and an empty . On a $2 \times n board, possible moves are restricted to shifting two columns while switching rows, yielding two disjoint paths: one connecting the squares in the first column of each row to subsequent positions, and another for the second column positions. For a $3 \times 3 board, the comprises an 8-cycle encompassing the border squares and an isolated central , as the center square has no valid knight moves within the bounds. The $4 \times 4 board produces a connected with 16 and 24 edges. Despite being connected, it has no or cycle. These examples illustrate how very small boards lead to isolated or multiple components, whereas the is connected on boards with dimensions at least 3×4 or 4×4 and larger. The number of edges in the knight's graph on an m \times n board with m, n \geq 2 is given by $4mn - 6(m + n) + 8, derived from counting valid moves in each of the eight directions while accounting for boundary losses. For square n \times n boards, this simplifies to $4(n-1)(n-2), or equivalently $4n^2 - 12n + 8. Rectangular boards differ from square ones primarily in edge distribution; for instance, narrow boards like $2 \times n have fewer edges per (at most 2), forming path-like structures, whereas square boards balance connectivity more evenly for n \geq 4. Toroidal variants modify the finite board by wrapping edges around, creating a where moves off one edge re-enter from side, resulting in a of degree up to 8 and often a circulant structure due to . On such boards, boundary effects vanish, enhancing connectivity; for example, the $4 \times 4 toroidal knight's graph is 4-regular and isomorphic to the 4-dimensional Q_4, which has 16 vertices and 32 edges. All toroidal knight's graphs remain bipartite, like their finite counterparts.

Properties

Structural properties

The knight's graph is bipartite, with the two partitions corresponding to the black and white squares of the standard coloring, as every changes the color of the square occupied by the piece. This bipartition ensures that there are no odd-length cycles in the graph. Consequently, the chromatic number of the knight's graph is 2, allowing the vertices to be colored using just two colors such that no adjacent vertices share the same color. As a , the knight's graph is perfect, meaning that in every , the size of the largest equals the chromatic number. The girth of the knight's graph—the length of its shortest cycle—is 4 for rectangular boards with dimensions m \geq 5 and n \geq 3, reflecting the presence of 4-cycles formed by sequences of knight moves that return to the starting vertex after four steps. For smaller boards, such as 3×3 or 4×4, the girth is larger due to boundary constraints limiting possible cycles. The standard 8×8 knight's graph is non-planar, as it contains 64 vertices and 336 edges, violating the planar graph bound of e \leq 3v - 6 = 186 edges for simple connected planar graphs with v \geq 3. This high edge density arises from the knight's multiple possible moves from most central positions, leading to numerous crossings when attempting to embed the graph in the plane without edge intersections. The of the knight's graph encodes the possible moves through a sparse 0-1 structure, where the entry at (i, j) is 1 if a can move from square i to square j in a single step, and 0 otherwise; these connections are determined by the eight fixed offsets (\Delta r, \Delta c) \in \{(\pm 1, \pm 2), (\pm 2, \pm 1)\}, adjusted for board boundaries.

Degree and connectivity

In the knight's graph, degrees vary based on the of the square on the board, reflecting the number of legal moves from that square. Interior vertices on large boards achieve the maximum of 8, as the can reach all eight possible L-shaped positions without going off the board. Degrees decrease toward the boundaries: on an 8×8 board, corner vertices have 2, near-corner edge vertices have 3, other edge vertices have 4 or 6, and near-center vertices reach 8. The average degree for an n×n knight's graph is given by the formula \frac{8(n-2)(n-1)}{n^2}, derived from twice the number of edges divided by the number of vertices, where the number of edges is $4(n-2)(n-1). For the standard 8×8 board, this yields an average degree of 5.25; for larger boards, it approaches 8 asymptotically. The knight's graph on an 8×8 board is connected, allowing the knight to reach any square from any other, with a diameter of 6—the maximum shortest path length between any pair of vertices. For smaller boards, connectivity differs significantly. The 3×3 knight's graph has two components: an 8-cycle formed by the border squares (each of degree 2) and an isolated central (degree 0). The 4×4 knight's graph is disconnected with two components, each comprising 8 vertices and preventing a full across the board. In contrast, the 5×5 knight's graph is connected, with 25 vertices and degrees ranging from 2 to 8.

Hamiltonian paths and cycles

On finite boards

In the knight's graph of a finite , a corresponds to an open , where the visits every square exactly once without returning to the starting position, while a represents a closed , where the returns to the start after visiting all squares. On an 8×8 board, closed knight's tours exist, with the first known solution attributed to in the early . Open tours are also possible from any starting square on this board. Hamiltonian s are impossible on boards with an odd number of squares, such as 1×1 or , because the knight's graph is bipartite with partitions of unequal size, preventing a that alternates between sets. For Hamiltonian paths on rectangular m × n boards (m ≤ n), open knight's tours exist if and only if mn ≥ 6 and the board is not one of the exceptions: 2×3, 2×4, , 3×4, or 4×4. On square n × n boards, they exist for all n ≥ 5 (with n=1 trivial). Computational methods for finding such tours on finite boards include algorithms, which systematically explore possible moves and retract invalid paths, and Warnsdorff's rule, a that prioritizes moves to squares with the fewest onward options to avoid dead ends. For example, the number of directed closed s on an 8×8 board is 26,534,728,821,064, as computed by Brendan McKay. Specific classifications of boards admitting cycles in the knight's graph are detailed in Schwenk's theorem.

Schwenk's theorem

Schwenk's theorem provides a complete of the rectangular chessboards on which a closed exists. For an m \times n board with m \leq n, a closed knight's tour is possible none of the following conditions hold: (a) m and n are both odd; (b) m = 1, 2, or $4; (c) m = 3 and n = 4, 6, or $8. This result resolves a long-standing question in graph theory and recreational mathematics, confirming that boards such as the standard $8 \times 8 admit closed tours, while exceptions like the $5 \times 5 (both dimensions odd) and $4 \times 6 (m=4) do not. Notably, the $6 \times 6 board, despite its even dimensions and size beyond the small exceptions, does support a closed tour. The proof relies on a combination of arguments, analysis, and exhaustive case studies for small values of m. For boards where both m and n are odd, the total number of squares is odd, rendering a impossible in the bipartite knight's , which requires even-length cycles. For m=1 or $2, the graph's low and linear structure prevent cycles covering all vertices. Cases with m=4 are addressed by considering the bipartition into outer rows (1 and 4) and inner rows (2 and 3), each of size 2n, showing through and arguments that no can exist. Finally, for m=3 and the specified n=4,6,8, detailed graph decompositions show that removing certain vertices disconnects the board into components too small for a full . For all other configurations, constructive methods—such as inductive extensions by adding strips of width 4—guarantee the existence of a closed tour. The theorem implies that nearly all rectangular boards larger than $4 \times 4 admit closed knight's tours, with failures confined to narrow strips (m \leq 4) or those with both dimensions odd, where the bipartite nature precludes cycles on odd-sized graphs. This classification highlights the knight's graph's robustness for cycles on sufficiently wide and even-total-square boards, influencing studies in . Extensions of similar results address non-rectangular variants, such as cylindrical boards where the m rows form a . Closed knight's tours exist on all such m × n cylindrical boards except for small cases like m=1 (any n), m=2 (n even, n>2), and m=4 (n=4). These results provide partial characterizations for modified topologies, paving the way for further generalizations to tori and higher-dimensional boards.

Infinite case

Definition

The infinite knight's graph is an undirected graph in that models the possible moves of a knight chess piece on an unbounded . Its vertex set consists of all points with integer coordinates in the plane, that is, \mathbb{Z}^2. Two vertices (x, y) and (x', y') are connected by an edge their difference corresponds to a standard , specifically one of the eight displacements (\pm 1, \pm 2) or (\pm 2, \pm 1). This graph is the of the \mathbb{Z}^2 generated by the symmetric set S = \{(\pm 1, \pm 2), (\pm 2, \pm 1)\}, where edges from a g \in \mathbb{Z}^2 connect to g + s for each s \in S. As a result, it is 8-regular, with every having exactly degree 8, and vertex-transitive, meaning there exists an mapping any to any other. The knight's graph is bipartite, with the two partite sets given by the even and odd classes of x + y \mod 2; each class is countably , as the knight's moves always change the parity of x + y. In contrast to finite-board variants, where boundary squares result in vertices of degree less than 8, the absence of boundaries ensures uniform degree throughout.

Key properties

The infinite is connected, meaning any two vertices can be linked by a finite of knight moves, although the graph's is due to its unbounded . The between any two specific points is finite. For large coordinates, this is approximately \frac{2}{3} \max(|x|, |y|), reflecting the knight's efficient L-shaped progression across the plane. The number of vertices reachable in exactly k steps from a starting point grows linearly for large k, specifically 28k - 20 for k ≥ 5, leading to a growth in the size of the ball of radius k, approximately 14k². This quadratic expansion underscores the graph's expansive structure, where the cumulative reachable positions form a roughly disk-like region scaled by the knight's movement constraints. Due to its infinite size, the infinite knight's graph admits no cycle, as any cycle must be finite. However, it contains paths of arbitrary finite length and one-way infinite (Hamiltonian rays visiting each vertex at most once and extending indefinitely), including constructions that visit every vertex exactly once in a spanning ray. The knight's moves generate the full integer lattice \mathbb{Z}^2 as a group under addition, ensuring reachability across the entire plane while respecting the bipartite nature of the graph (with parts defined by the parity of x + y). Although pairs of basis moves like (1,2) and (2,1) span a sublattice of index 3 (determinant -3), the full set of eight move directions fills the lattice completely. The adjacency operator of the infinite knight's graph, analyzed via Fourier transform on \mathbb{Z}^2, has a continuous spectrum determined by the symbol \sum_{v} e^{i \langle \theta, v \rangle} over the eight knight vectors v, yielding values ranging from -8 to 8; notable points in the spectrum include \pm \sqrt{8}, \pm \sqrt{5}, arising from alignments of the move generators with lattice directions.

Related graphs and applications

Other chess piece graphs

The king's graph represents the possible moves of a king on a chessboard, connecting each square to up to eight neighboring squares at distances of 1 or \sqrt{2} (horizontal, vertical, or diagonal adjacency). This structure results in a highly connected graph that is biconnected and admits Hamiltonian cycles on all boards with at least 4 squares (e.g., 2×2 and larger). In contrast, the bishop's graph features two disconnected components corresponding to the black and white squares of the chessboard, with edges linking squares along diagonal paths of any length within the same color class. The rook's graph, modeling straight-line horizontal and vertical moves, is the Cartesian product of two complete graphs K_n \square K_n on an n \times n board and is regular of degree $2(n-1), equivalent to the line graph of the complete bipartite graph K_{n,n}. The queen's graph combines the moves of the and , forming the of their sets, and achieves a maximum of 27 on an 8×8 board. Unlike the , which is bipartite due to its color-alternating L-shaped jumps of fixed length (two squares in one direction and one perpendicular), the is disconnected into color classes but not bipartite, as each component contains odd cycles from diagonal connections; the and queen's graphs also feature straight-line and combined connections that introduce odd cycles and higher connectivity without bipartiteness.

Applications in puzzles and theory

The knight's tour problem, which seeks a or cycle in the knight's graph, has long served as a classic puzzle in and . Solutions are typically found using algorithms like (DFS), which explore possible moves while marking visited vertices to avoid cycles, or heuristics such as Warnsdorff's rule that prioritize low-degree neighbors to reduce branching. These methods have applications in , particularly for in constrained environments, where the knight's graph models non-straight-line navigation in games or . Historically, Leonhard Euler's investigations into knight's tours in the 1750s provided early insights that prefigured modern , including systematic enumeration of paths on various board sizes and recognition of the problem's combinatorial structure, influencing the field's development beyond his earlier bridge work. In , the knight's graph exemplifies bipartite graphs, as knight moves always connect vertices of opposite colors on a checkered board, ensuring no odd-length cycles and enabling 2-coloring. It also illustrates problems, where finding a tour corresponds to a path visiting all vertices exactly once, and knight's distance—the shortest path length between squares—serves as a metric in chess engines for evaluating piece mobility and attack potentials. Variations extend the puzzle to three-dimensional boards, where a generalized (a, b, c)- requires visiting all cells in an L×M×N ; for instance, closed exist on 3×n×p boards under specific conditions but are impossible on boards with even dimensions or certain odd configurations. With obstacles, the problem adapts to incomplete graphs, testing partial around blocked . problems, meanwhile, seek the minimum set where every non-selected is adjacent to at least one selected, requiring 12 knights on an 8×8 board to cover all squares. Although deciding Hamiltonian paths in general graphs is NP-complete, the structured bipartite nature of the knight's graph allows efficient solutions for standard boards, contrasting with the broader theoretical intractability and highlighting its role in studying tractable special cases.

References

  1. [1]
    Knight Graph -- from Wolfram MathWorld
    Knight graphs are bipartite and therefore are perfect. The following table summarizes some named graph complements of knight graphs.
  2. [2]
    https://doi.org/10.1016/0166-218X(92)00170-Q
  3. [3]
    [PDF] Which Rectangular Chessboards Have a Knight's Tour? - IC-Unicamp
    Which Rectangular Chessboards Have a Knight's Tour? Author(s): Allen J. Schwenk ... We begin by showing why conditions (a), (b), and (c) must be excluded ...
  4. [4]
    [PDF] Knight's Tours and Zeta Functions - SJSU ScholarWorks
    A closed knight's tour is a Hamiltonian cycle on the knight graph associated with a chessboard.
  5. [5]
    [PDF] arXiv:2403.03907v1 [math.CO] 6 Mar 2024
    Mar 6, 2024 · ... knight's graph solely in terms of m, where m ≤ n. Theorem 8.1. The gonality of the m × n toroidal knight's graph is bounded by gon(Nt m×n) ...
  6. [6]
    [PDF] Graph theory notes - MSpace
    Dec 8, 2022 · ... Cycles and circuits. For positive integers m and n, let the knight's graph have mn vertices, each vertex corresponding to a square in an m×n ...
  7. [7]
    [PDF] On Rigidity of Unit-Bar Frameworks - UBC Math
    We will prove that F5,5(5) is infinitesimally rigid. The graph underlying F5,5(5) is the knight's graph, and so we refer to it as the 5×5 knight's framework,.
  8. [8]
    Knight's graph - Academic Dictionaries and Encyclopedias
    ... girth = 4 (if n ≥3, m ≥ 5) properties = In graph theory, a knight s tour ... Knight's graph. Knight's graph. infobox graph name = Knight's graph image_caption = ...
  9. [9]
    8.12. Building the Knight's Tour Graph - Runestone Academy
    To represent the knight's tour problem as a graph we will use the following two ideas: Each square on the chessboard can be represented as a node in the graph.
  10. [10]
    [PDF] 4.1 Undirected Graphs - Princeton CS
    Jan 26, 2010 · Can you draw the graph in the plane with no crossing edges? Graph ... knight's graph. legal knight moves a knight's tour. Page 713. 44.
  11. [11]
    Mathematics Dissertation 'The Knight's Tour' - Mark R. Keen
    The Knight's tour puzzle can be played in many different ways but the original, as far as I can tell, is to begin on an arbitrary square of the board and visit ...
  12. [12]
    How many moves needed for a knight to go from any square to any ...
    Mar 25, 2021 · You are asking for the diameter of the knight's graph. I suppose you only want it for the ordinary 8x8 chessboard.
  13. [13]
    Generalized knight's tours on rectangular chessboards - ScienceDirect
    We shall make use of the following necessary condition for the existence of a Hamiltonian path in a graph. If H is a graph, we let ...<|control11|><|separator|>
  14. [14]
    MATHEMATICAL RECREATIONS - jstor
    knight's tours might exist on an ordinary. 8× 8 chessboard. The first solutions were given soon after by Pierre de Mont- mort and Abraham de Moivre. The.
  15. [15]
    [PDF] Studies in Tours of Knight on Rectangular Boards - arXiv
    tour and its last cell are connected by knight's move, it is called re-entrant or closed knight tour else it is open knight tour. Generally, knight tours on ...<|control11|><|separator|>
  16. [16]
    https://www.mayhematics.com/t/1y.htm
  17. [17]
    [PDF] Warnsdorff's rule for finding knight's tour
    Warnsdorff's rule is a simple computational rule for finding knight's tours. It presents an attractive method for finding Hamil- ton paths in richly connected ...
  18. [18]
    [PDF] Knight's Tours of an 8 8 Chessboard Abstract. 1. Introduction. 2 ...
    The total number of undirected tours is 13,267,364,410,532 and the number of equivalence classes under rotation and re ection of the board is 1,658,420,855,433.
  19. [19]
    Arranging Countably Infinite Abelian Groups
    ### Summary of Infinite Knight's Graph as a Cayley Graph
  20. [20]
    Algebraic properties of graph of chess pieces - MathOverflow
    Dec 16, 2019 · The knight's graph is bipartite. The king's, rook's, queen's and bishop's graph are hamiltonian (and after Euler, it is very well-known ...<|separator|>
  21. [21]
    chess board knight distance - Math Stack Exchange
    Jun 22, 2019 · Is there a formula to compute the "knight distance" on an infinite board? ie how many step a knight need to move from (0,0) to any point (i,j)?Distance formula for generalized knight movement on infinite ...Infinite Knight's Tour - Mathematics Stack ExchangeMore results from math.stackexchange.com
  22. [22]
    Counting the Number of Squares Reachable in k Knight's Moves
    We obtain formulas for the number of squares reachable by a knight on an infinite chessboard in a minimum of k moves and for the cumulative number of squares ...Missing: sublattice | Show results with:sublattice
  23. [23]
    A knight's tour of an infinite chessboard
    Feb 22, 2024 · If you place a knight at the origin, there is a way for him to visit every point exactly once. It's possible to tour every point in a 5 × 5 lattice as shown ...
  24. [24]
    Can an $(a,b)$-knight reach every point on a chessboard?
    Jun 3, 2019 · The set of reachable positions with an (a,b) knight is a sublattice Λ of Z2 that is invariant under 90° rotation as well as vertical reflection.Knight move variant: Can it move from $A$ to $BInfinite nilpotent group, any normal subgroup intersects the center ...More results from math.stackexchange.com
  25. [25]
    King Graph -- from Wolfram MathWorld
    The m×n king graph is a graph with mn vertices in which each vertex represents a square in an m×n chessboard, and each edge corresponds to a legal move by a ...Missing: knight's | Show results with:knight's
  26. [26]
    Chessboard graphs - Graph Theory
    The 2-dimensional Knight Graph of parameters n and m is a graph with n m vertices in which each vertex represents a square in an n × m chessboard, and each edge ...<|control11|><|separator|>
  27. [27]
    Bishop Graph -- from Wolfram MathWorld
    A bishop graph is a graph formed from possible moves of a bishop chess piece, which may make diagonal moves of any length on a chessboard (or any other board).
  28. [28]
    Rook Graph -- from Wolfram MathWorld
    rook graph could also be called a "KK graph." It is equivalent to the line graph L(K_(m,n)) of the complete bipartite graph K_(m,n) , which is the ...
  29. [29]
    Queen Graph -- from Wolfram MathWorld
    The m×n queen graph Q_(m,n) is a graph with mn vertices in which each vertex represents a square in an m×n chessboard, and each edge corresponds to a legal ...Missing: union | Show results with:union
  30. [30]
    Given a 8x8 chessboard, what is the probability of randomly…
    Since there are 64 squares, the first queen can be placed in any of those 64 squares. Once placed, the second queen has 63 remaining squares to choose from.
  31. [31]
    None
    ### Formal Definition of the Knight's Graph
  32. [32]
    Knight's Shortest Path on Chessboard - Baeldung
    Mar 18, 2024 · In a knight's graph, each box on a chessboard denotes a vertex. Each vertex corresponds to the position of a knight on a chessboard. Each edge ...
  33. [33]
    Knight-Distance - Chessprogramming wiki
    The Knight-Distance between two squares determines the minimal number of moves a Knight needs, to reach one square from the other on the otherwise empty board.
  34. [34]
    Generalized knight's tour on 3D chessboards - ScienceDirect
    Aug 28, 2010 · A closed ( a , b , c ) -knight's tour is a series of ( a , b , c ) -knight's moves that visits every small cube of the L × M × N chessboard ...Missing: variations | Show results with:variations
  35. [35]
    Knights Problem -- from Wolfram MathWorld
    The problem of determining how many nonattacking knights K(n) can be placed on an n×n chessboard. For n=8, the solution is 32 (illustrated above).Missing: knight's | Show results with:knight's
  36. [36]
    [PDF] The Knight's Tour Problem and Rudrata's Verse
    Treating the knight's tour problem as a simpler instance of the more general Hamiltonian path problem in graph theory, attempts have been made for finding ...