Изменения

Перейти к: навигация, поиск

Теорема Хватала

15 байт убрано, 10:58, 15 октября 2011
Нет описания правки
Пусть теорема Хватала не верна, то есть существует граф с числом вершин <tex>\ n \ge 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>.
271
правка

Навигация