Утверждение истинно. Это классическая теорема Дирака; ниже — формулировка, краткая идея доказательства и обсуждение приложений.
Теорема Дирака. Пусть $G$ — простой неориентированный граф на $n$ вершинах, $n\ge 3$. Если минимальная степень $\delta (G)\ge n/2$, то $G$ гамильтонов (то есть содержит цикл, проходящий через все $n$ вершин).
Краткая идея доказательства (через теорему Ора). Сначала заметим, что условие Дирака даёт более сильное утверждение: для любых двух несмежных вершин $u,v$ выполняется
$$d(u)+d(v)\ge \delta (G)+\delta (G)\ge n,$$ поэтому выполняются условия теоремы Ора:
Теорема Ора. Если в простом графе на $n$ вершинах для любых несмежных $u,v$ верно $d(u)+d(v)\ge n$, то граф гамильтонов.
Идея доказательства Ора (схема): предположим противное, выберем максимально длинный простой путь $P=v_1{v}_2\dots v_k$. Тогда концы $v_1,v_k$ не смежны (иначе можно получить цикл и удлинить путь). Рассмотрим множества соседей $S$ вершины $v_1$ среди $v_2,\dots ,v_k$ и соседей $T$ вершины $v_k$ среди $v_1,\dots ,v_{k-1}$. Из максимальности пути следует, что никакой сосед $v_1$ не стоит непосредственно после соседа $v_k$ по пути, что даёт оценку $|S|+|T|\le k-1$. С другой стороны, условие Ора даёт $|S|+|T|=d(v_1)+d(v_k)\ge n$. Поскольку $k\le n$, выходит противоречие ($n\le |S|+|T|\le k-1\le n-1$). Значит противное неверно и граф гамильтонов. Из этой теоремы следует теорема Дирака.
Замечание о точности условия. Условие $\delta \ge n/2$ точно (в смысле границы): для чётного $n$ взятие двух полных графов $K_{n/2}$ без рёбер между ними даёт граф с $\delta =n/2-1$, не содержащий гамильтонова цикла.
Применимость в задачах маршрутизации и комбинаторной оптимизации
- Плюсы: условие Дирака даёт простую полиномиальную достаточную проверку гарантии существования гамильтонова цикла; полезно при проектировании сетей (гарантия маршрута, кольцевой обход, балансировка нагрузки), при построении тестовых случаев и предварительной фильтрации входов в алгоритмах для задачи о гамильтоновом цикле/оценке устойчивости сети.
- Ограничения: условие сильное и редко выполняется в разрежённых реальных сетях, оно только достаточное (не необходимое); не решает задачу поиска оптимального цикла для взвешенного TSP (NP‑трудность). Тем не менее при проектировании сетевой топологии с высокой связностью и при некоторых эвристиках/ограничениях может служить полезным критерием для гарантии существования обхода всех узлов.
- Практика: в алгоритмах проверки/поиска гамильтонова цикла условие можно использовать как быстрый тест; при положительном выводе — цикл можно построить по конструктивным частям доказательства (полиномиально), при отрицательном — требуется более тяжёлая комбинаторика или перебор.