Теорема о существовании простого цикла в случае существования цикла

Определение:

Простой (рёберно-простой) цикл в графе – цикл, в котором каждое из рёбер графа встречается не более одного раза.

Для удобства будем считать, что цикл задаётся [math]n[/math] вершинами и [math]n[/math] рёбрами: [math]V_0E_1V_1E_2 ... V_{n-1}E_n[/math], – причём ребро [math]E_i[/math] соединяет вершины [math]V_{i-1}[/math] и [math]V_{i % n}[/math].

Определение:

Длина цикла – количество рёбер, входящих в последовательность, задающую этот цикл.

Теорема:

Если две вершины графа лежат на цикле, то они лежат на простом цикле.