Индуктивный переход

Пусть G - это четный граф, имеющий k = n + 1 ребер.

Уже было доказано, что в G существует элементарный цикл ненулевой длины.

Пусть C - некоторый такой цикл в G.

Удалим из G все ребра цикла C. Нетрудно видеть, что, степени всех вершин полученного графа четные. Это так, поскольку при удалении из G ребер цикла C степень произвольной вершины графа G либо остается прежней, либо уменьшается на 2.

Полученный граф G ^*может оказаться несвязным. Однако для каждой компоненты связности G выполняются условия теоремы: она связная, не имеет петель, содержит только ориентированные ребра и является четным графом.

По предположению индукции в каждой из компонент связности графа G ^*существует цикл Эйлера. Обозначим эти циклы как C ₁,..., C_d.

Без ограничения общности можно считать, что каждый из этих циклов начинается и заканчивается в вершинах цикла C.

Общая схема расположения циклов C и C ₁,..., C_d в графе G приведена на рис. 5.19.

v

C _d G

C ₁ C

C_j

C_i

Рис. 5.19

Здесь пунктирной линией изображен цикл C, а замкнутые области соответствуют компонентам связности G ^*, в которых проведены циклы C ₁,..., C_d.

Организуем прохождение специального цикла в G, используя для этого циклы C, C ₁,..., C_d.

1. Возьмем вершину v, являющуюся началом цикла C.

2. Из этой вершины выполняется перемещение по C до тех пор, пока не встретится первая вершина, являющаяся началом еще не проходившегося цикла из C ₁,..., C_d, либо не будут пройдены все ребра _.

3. Если такой цикл C_i найден, то выполняется прохождение этого цикла, начинающееся и заканчивающееся в вершине, лежащей на C.

4. Если последняя вершина C_i не совпадает с v (т.е. пройдены не все ребра C), то повторим действия 2 - 4.

Через конечное число повторений действий 2 - 4 описанный выше процесс закончится. При этом каждое ребро цикла C и циклов C ₁,..., C_d проходится ровно один раз. Кроме того, проходятся все ребра G, так как C и C₁,..., C_d содержат все ребра этого графа.

Итак, последовательность вершин в определенном выше порядке их прохождения по графу G образует цикл Эйлера в том же графе.