Сделаю еще несколько замечаний по поводу поставленной задачи, чтобы не возникало иллюзий связанных с применением общеизвестных критериев гамильтоновости графа.
Пусть

связный граф, степень каждой вершины которого

(это необходимое условие).

.
Обозначим через

граф, вершинами которого

являются клетки шахматной доски

(

; далее считаем, что

), а его рёбрами

являются неупорядоченные пары клеток, "соединённых" ходом

-коня (или

-жирафа,

- чётное), т.е. можно сделать один ход

-жирафа из одной клетки пары в другую. Можно заметить, что

для любого

(при этом существуют вершины всех степеней в этом диапазоне). А вот для

:

. При этом для любого

ровно 4 вершины имеют степень 2.
Собственно известные критерии для гамильтоновости графа (удовлетворяющего необходимым условиям) используют условия наличия достаточно больших степеней у всех вершин.
1) Условие Дирака.

гамильтонов.
Для нашего

графа, очевидно не применимо.
2) Условие Оре.

гамильтонов.
Для

, очевидно, тоже не применимо, ибо для любых вершин (а не только несмежных)

, а у нас

.
3) Условие Поша. Вводится так называемая функция Поша целого неотрицательного аргумента

:
![\[
f(x)=\left|\left\{v\in V\mid d(v)\leqslant x\right\}\right|
\] \[
f(x)=\left|\left\{v\in V\mid d(v)\leqslant x\right\}\right|
\]](https://dxdy-04.korotkov.co.uk/f/7/4/3/7437f849886845345cd355e9d7b4529882.png)
Так вот, если

и в случае целого

, то

гамильтонов.
Для

- т.е. тоже не применимо.
4) Теорема Бонди-Хватала тоже не помогает. Граф является гамильтоновым тогда и только тогда, когда его замыкание — гамильтонов граф. А замыкание графа определяется добавлением ребра

для каждой пары несмежных вершин

и

, сумма степеней которых не меньше

.
Очевидно, что для

замыкание совпадает с самим графом.
Очевидно, что граф

не гамильтонов. Это проясняется следующей картинкой:

Значит имеем следующий промежуточный результат: либо

, либо

. Есть также гипотеза, что

. Для её подтверждения необходимо доказать, что не существует полного обхода жирафом доски

и представить (или доказать существование) полный обход доски

.