Изменения

Если <mathtex>n \ge geqslant 3</mathtex> и <mathtex>\operatorname{deg\ } u + \operatorname{deg \ } v \ge geqslant n</mathtex> для любых двух различных несмежных вершин <mathtex>\ u</mathtex> и <mathtex>\ v</mathtex> [[Основные определения теории графов#Неориентированные графы|неориентированного графа ]] '''<tex>G'''</tex>, то '''<tex>G''' </tex> {{--- }} [[Гамильтоновы графы | гамильтонов граф]].

Пусть, от противного, существует граф '''<tex>G'''</tex>, который удовлетворяет условию теоремы, но не является гамильтоновым графом.Будем добавлять к нему новые ребра до тех пор, пока не получим максимальный негамильтонов граф '''<tex>G''''</tex>. В силу того, что мы только добавляли ребра, условие теоремы не нарушилось.

Пусть <mathtex>\ u,v</mathtex> несмежные вершины в полученном графе '''<tex>G''''</tex>. Если добавить ребро <mathtex>\ uv</mathtex>, появится гамильтонов цикл. Тогда путь <mathtex>\ (u,v)</mathtex> {{--- }} гамильтонов.

Для вершин <mathtex>\ u,v</mathtex> выполнено <mathtex>\operatorname{deg\ } u + \operatorname{deg \ } v \ge geqslant n.</mathtex>

По принципу Дирихле, всегда найдутся две смежные вершины <mathtex>\ t_1,t_2</mathtex> на пути <mathtex>\ (u,v)</mathtex> ,т.е. <mathtex>u \ u..dots t_1t_2..\dots v</mathtex> , такие, что существует ребро <mathtex>\ ut_2</mathtex> и ребро <mathtex>\ t_1v.</mathtex>

Действительно, пусть <mathtex>\ S = </mathtex> { <mathtex> \{ i| \mid e_i=ut_{i+1} \in EG\}</mathtex> } и <mathtex>\ T = </mathtex> { <mathtex> \{ i| \mid f_i=t_iv \in EG\}</mathtex> }

Имеем: <mathtex>\left\vert S \right\vert + \left\vert T \right\vert = \operatorname{deg\ } u + \operatorname{deg \ } v \ge geqslant n </mathtex>, но <mathtex>\left\vert S + T \right\vert < n.</mathtex>

И тогда: Тогда <mathtex>\left\vert S\cap T \right\vert = \left\vert S \right\vert + \left\vert T \right\vert - \left\vert S+T \right\vert > 0</mathtex> , т.е. <mathtex>\exists i| : ut_{i+1}\in EG</mathtex> и <mathtex> t_iv \in EG.</mathtex>Получили противоречие, т.к. <mathtex>u \ u..dots t_1v..\dots t_2u</mathtex> {{--- }} гамильтонов цикл.