271
правка
Изменения
Нет описания правки
|proof=
Приведем доказательство от противного.
Пусть теорема Хватала не верна, то есть существует граф с числом вершин <tex>\ n \ge 3 </tex>, удовлетворяющий условию <tex>\ (*) </tex>, но не гамильтонов.
Будем добавлять в него [[Основные определения теории графов|рёбра]] до тех пор, пока не получим максимально возможный негамильтонов граф <tex> G </tex> (то есть добавление еще одного ребра сделает граф <tex> G </tex> гамильтоновым).
Важно то, что добавление рёбер не нарушает условие <tex>\ (*) </tex>.
