Изменения

Возьмём два существующих пути между нужными нам вершинами: <mathtex>V_0E_1V_1E_2V_2 ... E_nV_n</mathtex>, <mathtex>v_0e_1v_1e_2v_2 ... e_mv_m</mathtex>, <mathtex>V_0 = v_0</mathtex>, <mathtex>V_n = v_m</mathtex>. Удалим из них одинаковые префиксы и суффиксы, оставив из них только последние и первые вершины, соответственно. Оставшиеся пути: <mathtex>V_aE_{a+1} ... E_bV_b</mathtex>, <mathtex>v_ae_{a+1} ... e_cv_c</mathtex>, <mathtex>V_a = v_a</mathtex>, <mathtex>V_b = v_c</mathtex>, <mathtex>E_{a+1} \neq e_{a+1}</mathtex>, <mathtex>E_b \neq e_c</mathtex>.

Рассмотрим конкатенацию первого нового пути и развёрнутого второго нового пути. Она будет циклом, так как начальная и конечная вершины совпадают, изначально пути были рёберно-простыми, а в точке соединения, равно как и в точке замыкания цикла, условие различности двух идущих подряд рёбер выполняется. Мы получили цикл, определим его: <mathtex>V_0E_1V_1 ... E_kV_k</mathtex>, <mathtex>V_0 = V_k</mathtex>.

1. Для вершины <mathtex>V_i</mathtex> найдём момент её последнего вхождения в цикл – <mathtex>V_j</mathtex>. 2. Удалим отрезок цикла от <mathtex>E_{i+1}</mathtex> до <mathtex>V_j</mathtex>, включительно. Получившаяся последовательность вершин и рёбер графа останется циклом, и в нём вершина <mathtex>V_i</mathtex> будет содержаться ровно один раз.Начнём процесс с вершины <mathtex>V_1</mathtex> и будем повторять его каждый раз для следующей вершины нового цикла, пока не дойдём до последней. По построению, получившийся цикл будет содержать каждую из вершин графа не более одного раза, а значит, будет простым.