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>
Хватала
|statement=
Пусть '''G''' - [[Отношение связности, компоненты связности|связный граф]], количество вершин которого не меньше 3. Упорядочим степени вершин '''G''' по неубыванию.
Если для <tex>\forall k</tex> верна импликация <tex>(d_k \le k < n/2 \Rightarrow d_{n-k} \ge n-k) (*) </tex>,
то '''G''' - [[Гамильтоновы графы|гамильтонов]].
|proof=
Приведем доказательство от противного.
Пусть теорема Хватала не верна, есть граф : , где <tex>\ n \ge 3 </tex>, удовлетворяющий условию <tex>\ (*) </tex>, но не гамильтонов.
Будем добавлять в него ребра до тех пор, пока не получим максимально возможный негамильтонов граф '''G'''(т.е. добавление еще одного ребра сделает граф '''G''' гамильтоновым).
Добавление ребер не противоречит условию <tex>\ (*) </tex>.
Будем считать, <tex>\ degU \le degV </tex>.
Добавив к '''G''' новое ребро e = UV, получим гамильтонов граф '''G''' + UV.
Рассмотрим [[Гамильтоновы графы|гамильтонов цикл ]] графа '''G''' + UV : в нем обязательно присутствует ребро UV. <br>
Отбрасывая ребро UV, получим гамильтонову (U, V)-цепь в графе '''G''' : <tex>\ U = U_1 - U_2 - ... - U_n = V </tex>. <br>
Пусть <tex>\ S = \{i|e_i = U_1 U_{i+1} \in E(G)\} </tex> <br>
