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

От противного. Пусть G — не гамильтонов. Добавим к G минимальное количество новых вершин u₁, …,u_n, соединяя их со всеми вершинами G так, чтобы G’:= G + u₁ + … + u_n был гамильтоновым.

Пусть v, u₁, w, …,v — гамильтонов цикл в графе G’, причем v G, u₁ G’, u₁ G. Такая пара вершин v и u₁ в гамильтоновом цикле обязательно найдется, иначе граф G был бы гамильтоновым. Тогда w G, w {u₁,…,u_n}, иначе вершина u₁ была бы не нужна. Более того, вершина v несмежна с вершиной w, иначе вершина u₁ была бы не нужна.

Далее, если в цикле v,u₁,w, …,u’,w’, …,v есть вершина w’, смежная с вершиной w, то вершина v’ несмежна с вершиной v, так как иначе можно было бы построить гамильтонов цикл v,v’, …,w,w’, …,v без вершины u₁, взяв последовательность вершин w, …,v’ в обратном порядке. Отсюда следует, что число вершин графа G’, не смежных с v, не менее числа вершин, смежных с w. Но для любой вершины w графа G d(w) ≥ p/2+n по построению, в том числе d(v) ≥ p/2+n. Общее число вершин (смежных и не смежных с v) составляет n+p-1. Таким образом, имеем:

n+p-1 = d(v)+d(V) ≥ d(w)+d(v) ≥ p/2+n+p/2+n = 2n+p.

Следовательно, 0 ≥ n+1, что противоречит тому, что n > 0.

Теорема Оре. Если число вершин графа G(V,E) n ≥ 3 и для любых двух несмежных вершин u и v выполняется неравенство:

d(u)+d(v) ≥ n и (u,v) E, то граф G — гамильтонов.

Граф G имеет гамильтонов цикл если выполняется одно из следующих условий:

Условие Поша: d(v_k) ≥ k+1 для k < n/2.

Условие Бонди: из d(v_i) ≤ i и d(v_k)≤ k => d(v_i)+d(v_k)≥n (k≠i)

Условие Хватала: из d(v_k) ≤ k ≤ n/2 => d(v_n-k) ≥ n-k.

Далее, известно, что почти все графы гамильтоновы, то есть

где H(p) — множество гамильтоновых графов с p вершинами, а G(p) — множество всех графов с p вершинами. Таким образом, задача отыскания гамильтонова цикла или эквивалентная задача коммивояжера являются практически востребованными, но для нее неизвестен (и, скорее всего не существует) эффективный алгоритм решения.

Пример графа, когда не выполняется условие теоремы Дирака, но граф является гамильтоновым.

N = 8; d(v_i) = 3; 3 ≥ 8/2 = 4 не гамильтонов граф, но существует гамильтонов цикл: M = (1, 2, 3, 4, 5, 6, 7, 8, 1