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