Изменения

Пусть теорема Хватала не верна, то есть существует граф с числом вершин <tex>\ n \ge 3 </tex>, удовлетворяющий <tex>\ (*) </tex>, но негамильтонов.

Будем добавлять в него [[Основные определения теории графов|рёбра]] до тех пор, пока не получим максимально возможный негамильтонов граф <tex> G </tex> (то есть добавление еще одного ребра сделает граф <tex> G </tex> гамильтоновым).

Очевидно, что граф <tex>\ K_n </tex> гамильтонов для <tex>\ k \ge 3 </tex>.

Будем считать <tex> G </tex> максимальным негамильтоновым остовным подграфом графа <tex>\ K_n </tex>.