271
правка
Изменения
Нет описания правки
Выберем две несмежные вершины U и V графа '''G''' с условием : <math>\ degU + degV </math> - максимально.
Будем считать, <math>\ degU \le degV </math>.
Добавив к '''G''' новое ребро <math>\ e = UV </math>, получим гамильтонов граф '''G''' + UV.Рассмотрим гамильтонов цикл графа '''G''' + UV : в нем обязательно присутствует ребро UV. Отбрасывая ребро UV, получим гамильтонову цепь (U, V) в графе '''G''' : <math>\ U = U_1 - U_2 - ... - U_n = V </math>.
}}
