Существование гамильтоновых графов

Лемма. Любой граф G можно превратить в гамильтонов, добавив достаточное количество вершин и ребер.

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

К вершинам v₁, v₂, …, v_р добавим вершины u₁, u₂, …, u_р и множество ребер {(v _i,u _i)}U {(u _I,v_i+11)}. Получим гамильтонов граф.

Теорема Дирака. Если в графе G степень каждой вершины d (v) ≥ р /2 (р ─ число вершин), то этот граф является гамильтоновым.

Доказательство от противного.

Предположим, что граф не гамильтонов. Добавим к нему наименьшее количество п вершин u_{I ,} соединяя их со всеми вершинами v так, чтобы получился гамильтонов граф.

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

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

Р + п -1 ≥ d (w) + d(v) ≥ р /2 + п+ р /2 + п = р + 2п.

Итак, р+ п -1 ≥ р + 2п. Отсюда 0 ≥ п + 1, что противоречит положительности п.

Дата добавления: 2014-01-06