Дискретная математика: графы и автоматы. Альпин Ю.А - 13 стр.

§ 2. Эйлеровы и гамильтоновы графы                                13


“старой” вершиной. Ясно, что если добавить n новых вершин 10 ,
20 , . . . , n0 , то в таком расширенном графе есть гамильтонов цикл
1 − 10 − 2 − 20 − . . . − n − n0 − 1. Пусть k > 0 — наименьшее ко-
личество новых вершин, после добавления которых граф становится
гамильтоновым. Рассмотрим гамильтонов цикл p − q − r − . . . − p в
новом графе. Можно считать, что p, r — несмежные старые вершины,
а q — новая (почему?). Докажем вспомогательное утверждение: после
каждой вершины, смежной с p, следует вершина, не смежная с r.
Предположим, случилось противное и цикл имеет вид


где s смежна с p, а t смежна с r. Но тогда существует цикл




обозначенный стрелками. Как видим, новая вершина q оказывается
лишней, но это противоречит минимальности числа k новых вершин.
Итак, наше вспомогательное утверждение верно. Но тогда число вер-
шин, не смежных с r, не меньше числа вершин, смежных с p, то есть,
не меньше, чем n/2 + k. С другой стороны, число вершин, смежных
с r, тоже не меньше, чем n/2 + k. Следовательно, общее количество
вершин в расширенном графе не меньше, чем n + 2k, то есть, полу-
чено неравенство n + k > n + 2k, верное лишь при при k = 0, что
противоречит предположению о негамильтоновости графа. ¤
    Интересно, что изменив лишь окончание доказательства преды-
дущей теоремы, можно получить более точный результат, известный
как теорема Оре (1960).
   Теорема 3. Для существования гамильтонова цикла в графе с
n > 3 вершинами достаточно, чтобы сумма степеней любых двух
несмежных вершин была не меньше n.
   Д о к а з а т е л ь с т в о. Вначале повторяем доказательсто
теоремы Дирака, включая вспомогательное утверждение и его след-
ствие: число вершин, несмежных с r в расширенном графе, не меньше
суммы степени вершины p в исходном графе и числа k добавленных
вершин. А дальше будем рассуждать так. Поскольку степень верши-
ны r в новом графе равна её степени в старом графе и числа k, то,
учитывая условие теоремы, количество вершин в расширенном графе
должно удовлетворять неравенству:
            n + k > степень p + степень r + 2k > n + 2k.