Это теорема Дирака $(1952)$. Докажем от противного. Предположим, что $G$ не содержит гамильтонова цикла. Добавим рёбра до получения максимального графа без гамильтонова цикла. Пусть $u$ и $v$ — несмежные вершины, причём добавление ребра $(u,v)$ создаёт гамильтонов цикл. Тогда существует гамильтонов путь $v_1=u, v_2$, ..., $v_n=v$. Пусть $A$ — множество $i$ таких, что $(u, v_{i+1})$ — ребро, $B$ — множество $i$ таких, что $(v_i, v)$ — ребро. Тогда $|A| = deg(u) \geq \frac{n}{2}, |B| = deg(v) \geq \frac{n}{2}$. Оба A, B — подмножества $\{1,\ldots,n-1\}$, значит $|A|+|B| \geq n > n-1$, поэтому $A$ и $B$ пересекаются. Для некоторого $i: (u, v_{i+1})$ и $(v_i, v)$ — рёбра. Тогда $u, v_{i+1}, v_{i+2}$, ..., $v_n=v, v_{i}, v_{i-1}$, ..., $v_1=u$ — гамильтонов цикл. Противоречие.

💡 Авторизуйтесь, чтобы получить помощь AI-тьютора с подсказками и решениями!