Теорема Дирака.

Если для графа G |G|=n³3 и для любой вершины v графа G deg(v)³n/2, то в G есть гамильтонов цикл.

Доказательство.

При n=3 условиям удовлетворяет лишь 1 граф - треугольник, а он имеет гамильтонов цикл. Рассмотрим теперь n>3. Пусть вершины графа - рыцари, причем рыцари дружат между собой, если между соответствующими вершинами в G есть ребро и враждуют в противном случае. В новых обозначениях требуется расставить рыцарей по кругу так, чтобы ни один из них не враждовал с соседями, причем каждый рыцарь знает ³n/2 рыцарей. В начале расставим их произвольно. Пусть количество пар соседей-рыцарей, враждующих между собой есть V. Тогда V£n. Возьмем пару соседних рыцарей, которые враждуют между собой. Назовем одного из рыцарей пары - рыцарем №1, чтобы следующий по часовой стрелке рыцарь был второй из пары и назовем его рыцарем №2. Докажем, что среди остальных (n-2) рыцарей есть пара соседних рыцарей, один из которых друг №1, другой - друг №2, чтобы друг №1 в паре стоял первым по часовой стрелке, а друг №2 - вторым (на рисунке слева изображены рыцари 1 и 2, а также их друзья - 1' и 2'). Докажем это утверждение от противного: пусть такой пары рыцарей среди оставшихся (n-2) не найдется (1). Заметим, что у №1 и №2 среди оставшихся рыцарей по ³[n+1]/2 другу. Тогда будем рассматривать ³[n+1]/2 пару: друг рыцаря №1 и следующий за ним по часовой стрелке. Тогда по (1) следующие за этими ³[n+1]/2 рыцарями не могут быть друзьями 2. Тогда среди n-2 рыцарей (без №1 и №2) ³[n-1]/2 рыцарь недруг (2) (последним другом 1 мог оказаться рыцарь-сосед 1 (но не №2)). Но тогда количество друзей у №2 £(n-2)-[n-1]/2=[n-2]/2<n/2, чего не могло быть по условиям. Отсюда (1) верно. Но тогда возьмем всех рыцарей от 2 до 1' и посадим их наоборот (1' - на место 2, ..., 2 - на место 1'). Тогда количество пар соседей-рыцарей, враждующих между собой станет £V-1. Отсюда за £V таких операций мы придем к расположению рыцарей без враждующих рыцарей-соседей. Отсюда верна и теорема Дирака в своей начальной формулировке.