Изменения

Возьмём любой из существующих путей между нужными нам вершинами: <tex>V_0E_1V_1E_2V_2 v_0e_1v_1e_2v_2 ... E_nV_ne_nv_n</tex>.

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

Тогда в нём содержатся две одинаковые вершины <tex>V_i v_i = V_jv_j</tex>, <tex>i < j</tex>. Удалим из исходного пути отрезок от <tex>E_e_{i+1}</tex> до <tex>V_jv_j</tex>, включительно. Конечная последовательность также будет путём от <tex>V_0v_0</tex> до <tex>V_nv_n</tex> и станет короче исходной. Получено противоречие с условием: взятый нами путь оказался не кратчайшим. Значит, предположение неверно, выбранный путь – простой.