Теорема Оре

Теорема:

Если [math]n \ge 3[/math] и [math]deg\ u + deg \ v \ge n[/math] для любых двух различных несмежных вершин [math]\ u[/math] и [math]\ v[/math] графа G, то G - гамильтонов граф.

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

[math]\triangleright[/math]

Пусть, от противного, существует граф G, который удовлетворяет условию теоремы, но не является гамильтоновым графом. Будем добавлять к нему новые ребра до тех пор, пока не получим максимальный негамильтонов граф G'. В силу того, что мы только добавляли ребра, условие теоремы не нарушилось. Пусть [math]\ u,v[/math] несмежные вершины в полученном графе G'. Если добавить ребро [math]\ uv[/math], появится гамильтонов цикл. Тогда путь [math]\ (u,v)[/math] - гамильтонов. Для вершин [math]\ u,v[/math] выполнено [math]deg\ u + deg \ v \ge n[/math]. По принципу Дирихле, всегда найдутся две смежные вершины [math]\ t_1,t_2[/math] на пути [math]\ (u,v)[/math] ,т.е. [math]\ u..t_1t_2..v[/math] , такие, что существует ребро [math]\ ut_2[/math] и ребро [math]\ t_1v[/math]. Получили противоречие, т.к. [math]\ u..t_1v..t_2u[/math] - гамильтонов цикл.

[math]\triangleleft[/math]