Определение

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

Заметим, что в четных графах возможны изолированные вершины, имеющие степень 0.

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

Для таких графов справедливо следующее утверждение.

ТЕОРЕМА 5.5 (Теорема Эйлера)

Граф G имеет цикл Эйлера тогда и только тогда, когда он является четным графом.

Доказательство

Необходимость. ( ) Пусть G имеет цикл Эйлера и С  это некоторый такой цикл в G.

1. Всякое прохождение внутренней вершины цикла С использует ровно два ребра, выходящих из этой вершины.

2. Первое и последнее рёбра, проходимые при движении по циклу, образуют еще одну пару ребер, инцидентные такой вершине цикла, которая является начальной и заключительной одновременно.

Поэтому степень каждой вершины графа четная. Следовательно, G является четным графом.

Достаточность. ( )

Покажем, что всякий четный граф G = (V, U) имеет цикл Эйлера.

Если G содержит единственную вершину, то доказываемое утверждение очевидно, поскольку такой граф не имеет ребер и единственный цикл Эйлера в нем  это цикл длины 0.

Рассмотрим случай, когда G имеет хотя бы одно ребро.

1. Покажем, что всякий четный граф с непустым множеством ребер G имеет элементарный цикл, длина которого не меньше 3.

Пусть v₁  это некоторая вершина из V. Возьмем произвольное ребро (v₁, v₂), выходящее из v₁, и перейдем по нему в вершину v₂.

Поскольку степень v₂ является четной, то из этой вершины выходит еще хотя бы одно ребро. Возьмем любое такое ребро (v₂,v₃) и продолжим движение в графе G.

Движение по G продолжаем до тех пор, пока очередное выбранное ребро не приведет в одну из уже пройденных вершин. Выделим вершину, которая встретилась второй раз.

Поскольку множество вершин в G является конечным, то описанный процесс закончится за конечное число шагов.

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

2. Покажем, что в G имеется цикл Эйлера.

Докажем это индукцией по числу k ребер в графе G.

Базис индукции

Пусть k = 3. Нетрудно проверить, что это минимальное количество ребер в четном графе, содержащем хотя бы одно ребро. Тогда все ребра G образуют из цикла длины 3, который и является тривиальным циклом Эйлера в таком графе.

Индуктивное предположение

Предположим, что для каждого чётного графа с k n ребрами доказываемое утверждение верно.

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

Пусть 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 образует цикл Эйлера в том же графе.

Доказательство окончено.

Приведенное доказательство достаточности фактически содержит рекурсивный алгоритм построения цикла Эйлера в произвольном графе. Такой алгоритм основан на нахождениив этом графе элементарного цикла, длина которого больше 3. В дальнейшем выполняется рекурсивное построение циклов Эйлера в четных связных подграфах, получаемых из исходного графа после удаления ребер найденного элемеентарного цикла.

Теорема Эйлера была доказана выше для графов, удовлетворяющих ряду ограничений. Но ее можно обобщить на случай графов, которые являются ориентированными или содержат петли.

При этом приведенное доказательство теоремы требует незначительных уточнений в формулировках и рассуждениях.

Например, для ориентированных графов доказательство теоремы Эйлера остается справедливым, если дополнительно потребовать, чтобы число ребер, выходящих из всякой вершины, равнялось числу ребер, ведущих в эту вершину.

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

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

Требование связности графа является существенным для существования циклов Эйлера в графах. Если это условие не выполняется, но справедливы остальные условия теоремы Эйлера, то можно утверждать, что в каждой компоненте связности графа имеется цикл Эйлера.

Упражнение. Сформулировать и доказать обобщение теоремы Эйлера на случай ориентированных графов.