Изменения
Нет описания правки
Воспользуемся доказанной выше леммой. Так как в нашем графе существует цикл, то существуют два реберно-простых пути между некоторыми вершинами: <tex>v_0e_1v_1e_2v_2 ... e_nv_n</tex>, <tex>v'_0e'_1v'_1e'_2v'_2 ... e'_mv'_m</tex>, <tex>v_0 = v'_0</tex>, <tex>v_n = v'_m</tex>. Удалим из путей одинаковые префиксы и суффиксы, оставив из тех только последние и первые вершины, соответственно. Оставшиеся пути: <tex>v_ae_{a+1} ... e_bv_b</tex>, <tex>v'_ae'_{a+1} ... e'_cv'_c</tex>, <tex>v_a = v'_a</tex>, <tex>v_b = v'_c</tex>, <tex>e_{a+1} \neq e'_{a+1}</tex>, <tex>e_b \neq e'_c</tex>.
Рассмотрим конкатенацию первого нового пути и развёрнутого второго нового пути. Она будет циклом, так как начальная и конечная вершины совпадают, изначально пути были рёберно-простыми, а в точке соединения, равно как и в точке замыкания цикла, условие различности двух идущих подряд рёбер выполняется. Мы получили цикл, определим его: <tex>v_0e_1v_1 ... e_kv_k</tex>, <tex>v_0 = v_k</tex>.Дальше будем действовать по следующему алгоритму:
* Алгоритм:
