Knight's graph

Knight's graph
${\displaystyle 8\times 8}$ knight's graph
Vertices	${\displaystyle mn}$
Edges	${\displaystyle 4mn-6(m+n)+8}$
Girth	4 (if ${\displaystyle n\geq 3}$ and ${\displaystyle m\geq 5}$)
Properties	bipartite

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 ${\displaystyle m\times n}$ knight's graph is a knight's graph of an ${\displaystyle m\times n}$ chessboard. Its vertices can be represented as the points of the Euclidean plane whose Cartesian coordinates ${\displaystyle (x,y)}$ are integers with ${\displaystyle 1\leq x\leq m}$ and ${\displaystyle 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 ${\displaystyle {\sqrt {5}}}$.