Изменения

Если <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>.В силу того, что мы только добавляли ребра, условие теоремы не нарушилось. Пусть <tex>u,v</tex> несмежные вершины в полученном графе <tex>G'</tex>. Если добавить ребро <tex>uv</tex>, появится гамильтонов цикл. Тогда путь <tex>(u,v)</tex> {{---}} гамильтонов. Для вершин <tex>u,v</tex> выполнено <tex>\operatorname{deg} u + \operatorname{deg} v \geqslant n.</tex>  По принципу Дирихле всегда найдутся две смежные вершины <tex> t_1,t_2</tex> на пути <tex>(u,v)</tex>, т.е. <tex>u \dots t_1t_2 \dots v</tex> , такие, что существует ребро <tex>ut_2</tex> и ребро <tex>t_1v.</tex> Действительно, пусть <tex>S=</tex> <tex>\{ i \mid e_i=ut_{i+1} \in EG \}</tex> и <tex>T = </tex> <tex>\{ i \mid f_i=t_iv \in EG \}</tex>  Имеем: <tex>\left\vert S \right\vert + \left\vert T \right\vert = \operatorname{deg} u + \operatorname{deg} v \geqslant n </tex>, но <tex>\left\vert S + T \right\vert < n.</tex> Тогда <tex>\left\vert S\cap T \right\vert = \left\vert S \right\vert + \left\vert T \right\vert - \left\vert S+T \right\vert > 0</tex>, т. е. <tex>\exists i: ut_{i+1}\in EG</tex> и <tex> t_iv \in EG.</tex>Получили противоречие, т. к. <tex>u \dots t_1v \dots t_2u</tex> {{---}} гамильтонов цикл.