Граф ходов коня

В теории графов графом ходов коня называется граф, изображающий все возможные ходы коня на шахматной доске — каждая вершина соответствует клетке на доске, а рёбра соответствуют возможным ходам[1].

Граф ходов коня
Граф ходов коня 8 × 8
Вершин	nm
Рёбер	4mn - 6(m + n) + 8
Обхват	4 (если n ≥ 3, m ≥ 5)

Для графа ходов коня на доске размера ${\displaystyle n\times m}$ число вершин равняется ${\displaystyle nm}$. Для доски ${\displaystyle n\times n}$ число вершин равняется ${\displaystyle n^{2}}$, а число рёбер равняется ${\displaystyle 4(n-2)(n-1)}$.

Нахождение гамильтонова пути для графа ходов коня — это задача об обходе доски конём[1]. Теорема Швенка (Schwenk) даёт размеры шахматных досок, для которых возможен обход конём[2].