Назовём два пути одинаковыми, если последовательности вершин и рёбер графа, задающие их, совпадают полностью. Иначе будем считать пути различными.
{{Теорема
|statement=
Если между двумя [[Основные определения теории графов|вершинами неориентированного графа]] существуют два различных рёберно-простых [[Основные определения теории графов|пути]], то в этом графе существует простой цикл.
|proof=
Для доказательства этой теоремы введём определение.
{{Определение
|definition=
'''Простой (рёберновершинно-простой) цикл''' в графе – [[Основные_определения_теории_графов#ЦиклОсновные определения теории графов|цикл]], в котором каждое каждая из рёбер вершин графа встречается не более одного раза.
}}
Для удобства будем считатьОчевидно, это условие не распространяется на первую и последнюю вершины цикла. Возьмём два существующих пути между нужными нам вершинами: <math>V_0E_1V_1E_2V_2 ... E_nV_n</math>, <math>v_0e_1v_1e_2v_2 ... e_mv_m</math>, что цикл задаётся <math>nV_0 = v_0</math> вершинами и , <math>nV_n = v_m</math> рёбрами. Удалим из них одинаковые префиксы и суффиксы, оставив из них только последние и первые вершины, соответственно. Оставшиеся пути:<math>V_0E_1V_1E_2 V_aE_{a+1} ... V_E_bV_b</math>, <math>v_ae_{n-a+1}E_n... e_cv_c</math>, <math>V_a = v_a</math>, – причём ребро <math>E_iV_b = v_c</math> соединяет вершины , <math>V_E_{i-a+1} \neq e_{a+1}</math> , <math>E_b \neq e_c</math>. Рассмотрим конкатенацию первого нового пути и развёрнутого второго нового пути. Она будет циклом, так как начальная и конечная вершины совпадают, изначально пути были рёберно-простыми, а в точке соединения, равно как и в точке замыкания цикла, условие различности двух идущих подряд рёбер выполняется. Мы получили цикл, определим его: <math>V_{i % n}V_0E_1V_1 ... E_kV_k</math>, <math>V_0 = V_k</math>.
{{Определение* Алгоритм:|definition= 1. Для вершины <math>V_i</math> найдём момент её последнего вхождения в цикл – <math>V_j</math>.'''Длина 2. Удалим отрезок цикла''' – количество от <math>E_{i+1}</math> до <math>V_j</math>, включительно. Получившаяся последовательность вершин и рёберграфа останется циклом, входящих и в последовательностьнём вершина <math>V_i</math> будет содержаться ровно один раз.Начнём процесс с вершины <math>V_1</math> и будем повторять его каждый раз для следующей вершины нового цикла, пока не дойдём до последней. По построению, задающую этот получившийся циклбудет содержать каждую из вершин графа не более одного раза, а значит, будет простым.
}}
{{Теорема== Замечания ==* Наличие двух различных рёберно-простых путей между какими-либо вершинами графа равносильно наличию [[Основные определения теории графов|statement=цикла]] в этом графе.* Так как вершинно-простой путь всегда является рёберно-простым, данная теорема справедлива и для вершинно-простых путей (усиление условия).* Так как вершинно-простой цикл всегда является рёберно-простым, данная теорема справедлива и для рёберно-простого цикла (ослабление результата).* Утверждение Если две вершины графа лежат на цикле, то они лежат на простом цикле.|proofв общем случае неверно, так как эти вершины могут лежать в разных компонентах вершинной или рёберной двусвязности: все пути из одной вершины в другую будут содержать одну и ту же точку сочленения или один и тот же мост. == См. также ==}}* [[Теорема о существовании простого пути в случае существования пути]]
[[Категория: Алгоритмы и структуры данных]]
[[Категория: Основные определения теории графов]]
