Короткий ответ: да — это сразу следует из теоремы Дирака: если в простом графе на $n\ge 3$ вершинах минимальная степень $\delta (G)\ge n/2$, то граф содержит гамильтонов цикл, а значит и гамильтонов путь.
Краткий набросок доказательства (по Дираку, стандартный вариант):
- Предположим противное: пусть $G$ не содержит гамильтонова цикла. Возьмём самый длинный цикл $C$ в $G$; пусть $|V(C)|=m<n$.
- Любая вершина $x\notin V(C)$ имеет не менее $n/2$ соседей в $G$, а все её соседи лежат на цикле $C$ (иначе можно было бы удлинить цикл). Так как $m<n$, по принципу Дирaка существует пара соседей $u,v$ на $C$, которые являются смежными вершинами на цикле — тогда можно «вставить» $x$ между $u$ и $v$, получив больший цикл, противоречие.
- Следовательно, $m=n$ и $C$ — гамильтонов цикл. Это завершает доказательство; гамильтонов путь следует автоматически.
Возможные улучшения и обобщения (сильнее или более гибкие условия):
- Теорема Ора: если для любых двух несмежных вершин $u,v$ выполнено $\mathrm{deg}(u)+\mathrm{deg}(v)\ge n$, то $G$ гамильтонов. Это обобщает условие Дирака.
- Теорема Бонди—Хватал (closure): замыкая граф добавлением ребра между любыми несмежными $u,v$ с $\mathrm{deg}(u)+\mathrm{deg}(v)\ge n$ до тех пор, пока можно, — граф гамильтонов тогда и только тогда, когда его замыкание — полный граф. Это даёт мощный алгоритмический критерий.
- Теоремы Хватала и другие условия на последовательность степеней дают ещё более тонкие достаточные условия.
Ограничения и острость условия:
- Условие Дирака достаточно, но не необходимо: существуют гамильтоновы графы с гораздо меньшей минимальной степенью.
- Порог $n/2$ в общем смысле лучший: его нельзя существенно снизить. Простейший пример «показательной» негодности снижения — для чётного $n=2k$ полный двудольный граф $K_{k-1,k+1}$ имеет $\delta =k-1=n/2-1$ и не содержит гамильтонова цикла (части разного размера запрещают цикл, проходящий через все вершины). Аналогичные примеры показывают, что требование $\delta \ge n/2$ нельзя заменить на $\delta \ge n/2-1$ в общем виде.
Замечания:
- Условие предполагает простой неориентированный граф. В ориентированных графах есть свои критерии (напр., теорема Гёравца и др.).
- Для практики часто удобнее проверять условия Ора или замыкание Бонди—Хватала, они более гибкие.