271
правка
Изменения
Нет описания правки
Будем считать, <math>\ degU \le degV </math>.
Добавив к '''G''' новое ребро <math>\ e = UV </math>, получим гамильтонов граф '''G''' + UV.
Рассмотрим гамильтонов цикл графа '''G''' + UV : в нем обязательно присутствует ребро UV. <br>Отбрасывая ребро UV, получим гамильтонову (U, V)-цепь в графе '''G''' : <math>\ U = U_1 - U_2 - ... - U_n = V </math>. <br>
Пусть <math>\ S = \{i|e_i = U_1 U_{i+1} \in E(G)\} </math> <br>
Пусть <math>\ T = \{i|f_i = U_i U_n \in E(G)\} </math> <br>
