271
правка
Изменения
Нет описания правки
В [[Основные определения теории графов|графе]]: <tex>\ G </tex>, состоящем из <tex>\ n </tex> [[Основные определения теории графов|вершин]], <tex>\ d_i </tex> - [[Основные определения теории графов|степень ]] <tex>\ i </tex> - ой вершины. <br>
Все <tex>\ d_i </tex> расположены в порядке неубывания. <br>
<tex>\ (*): </tex> <tex>\forall k</tex> верна импликация <tex>(d_k \le k < n/2 \Rightarrow d_{n-k} \ge n-k)</tex> <br>
|proof=
Приведем доказательство от противного.
Пусть теорема Хватала не верна, есть граф: , где <tex>\ n \ge 3 </tex>, удовлетворяющий условию <tex>\ (*) </tex>, но не гамильтонов.Будем добавлять в него [[Основные определения теории графов|ребра ]] до тех пор, пока не получим максимально возможный негамильтонов граф '''G'''(т.е. добавление еще одного ребра сделает граф '''G''' гамильтоновым).
Добавление ребер не противоречит условию <tex>\ (*) </tex>.
Очевидно, что граф <tex>\ K_n </tex> гамильтонов для <tex>\ k \ge 3 </tex>.
