Гамильтоновы пути и циклы

Если граф связен и $2e \geq n^{2} - 3n + 6$, то в нём есть гамильтонов цикл.

Теорема Дирака — Оре. Граф, сумма степеней любых двух несмежных вершин которого не меньше $n$, имеет гамильтонов цикл.

Лемма Дирака. Если $a_{0} \ldots a_{s}$ — максимальный из путей в графе, проходящих по каждой своей вершине только один раз, $s \geq 3$ и $\deg a_{0} + \deg a_{s} > s$, то в этом графе есть несамопересекающийся цикл длины $s$.

Если в связном графе есть несамопересекающийся цикл длины $s < n$, то в этом графе есть путь длины $s$, проходящий по каждой своей вершине только один раз.

Граф, сумма степеней любых двух несмежных вершин которого не меньше $n-1$, имеет гамильтонов путь.

В этом графе есть хотя бы один несамопересекающийся цикл.

Обозначим через $v_{1}, \ldots , v_{s}$ максимальный несамопересекающийся цикл в этом графе. Обозначим через $W$ любую компоненту связности графа, полученного удалением вершин этого несамопересекающегося цикла из исходного графа. Обозначим через $X$ множество вершин несамопересекающегося цикла, соседних с $W$.

Тогда $\left|X\right| \geq k$.

Вершины $v_{i}, v_{i+1}$ не лежат одновременно в $X$.

Если $v_{i}, v_{j} \in X$, то в графе нет ребра $v_{i+1} v_{j+1}$.

Есть ли гамильтонов путь в графе на рис. 8?

Рис. 8. Есть ли в этом графе гамильтонов путь?

Есть ли гамильтонов цикл в графе на рис. 9?

Рис. 9. Граф многогранника Гринбергса. Есть ли в нём гамильтонов путь?

Для каких $n$ есть гамильтонов цикл в графе, вершинами которого являются 3-элементные подмножества $n$-элементного множества, и два подмножества соединены ребром, если они пересекаются ровно по одному элементу?

В любом турнире имеется ориентированный гамильтонов путь.

Для любого $n$ существует турнир с $n$ вершинами, в котором имеется не менее $n! / 2^{n}$ ориентированных гамильтоновых путей.