Доказательство окончено. Пусть G = (V, U) - неориентированный связный граф без петель и |V| =r

СЛЕДСТВИЕ (Теорема Дирака)

Пусть G = (V, U) - неориентированный связный граф без петель и |V| = r. Тогда если для всякой вершины v Î V справедливо неравенство d (v) , то G имеет цикл Гамильтона.

Заметим, что приведенное доказательство теоремы 5.6 является конструктивным, поскольку оно содержит явный алгоритм построения цикла Гамильтона во всяком графе, для которого выполняются условия этой теоремы.