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

1Þ 2

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

2Þ 3

G - связный и нетривиальный граф, следовательно для . Степени вершин четные, а это означает, что для , . Мы знаем, что или q > p- 1, q=|E|, p=|V|.

Следовательно, граф G – не дерево (в дереве q=p-1), а значит, граф G содержит, по крайней мере, один простой цикл . - это количество ребер, определяющих цикл. Рассмотрим граф G- (уберем все ребра цикла и исключим из него все изолированные вершины). Степени вершин полученного графа G₂ будут четные (убирая цикл из каждой вершины, которая по условию имеет четную степень, убираем 2 инцидентных ребра). Таким образом, в графе G₂ также будет существовать простой цикл, обозначим его . Продолжаем выделение простых циклов до тех пор, пока не получим пустой граф. Имеем и .

3 1

Возьмем какой-либо цикл из разбиения графа G на простые циклы. Если Е= , то теорема доказана. Если нет, то существует цикл , не имеющий общих ребер с , но такой, что , так как граф G связан.

Маршрут является циклом и содержит все свои ребра по одному разу. Если Е= , то теорема доказана. Если нет, то существует цикл , такой что . Далее будем наращивать Эйлеров цикл, пока он не исчерпает разбиения.

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

Обозначим исходный граф Г₀. В процессе выполнения алгоритма из графа Г₀ будут удаляться ребра и будет порождена последовательность графов Г_0, Г₁, …, Г_к.

1.Начиная с произвольной вершины х₀ присвоить любому ребру (х_0, х₁) номер 1. Удалив ребро (х_0, х₁) из массива ребер графа Г₀, получаем граф Г₁. Перейти к вершине х_1.

2.Пусть х_к – вершина, в которую осуществлен переход после очередного шага нумерации ребра, получившего номер к. Для дальнейшей нумерации выбираем любое ребро графа Г_к, инцидентное в вершине х_к с учетом следующего правила: ребра, удаление которых из графа Г_к повлечет нарушение его связности, выбираются только тогда, когда другой выбор осуществить нельзя. То есть ребро, являющееся мостом, выбирается в последнюю очередь. Алгоритм заканчивает работу, когда получен цикл (выбрано ребро (х, х₀), где х – некоторая вершина графа Г₀)

Пример

Сначала проверим, все ли вершины имеют четную степень.

В качестве начальной вершины возьмем – 4.

1. 4 - (4, 2) – 1

2. 2 - (2, 3) – 2

3. 3 - (3, 1) – 3, ребро (3, 4) брать нельзя – нарушается связность

4. 1- (1, 2) – 4

5. 2 - (2, 5) – 5

6. 5 - (5, 6) – 6

7. 6 - (6, 3) – 7

8. 3 - (3, 4) – 8

Если мы разработаем некий алгоритм, то желательно показать, что он решает именно то, что мы хотели, то есть алгоритм надо обосновать. Давайте проверим обоснование алгоритма Флери.

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

Алгоритм, очевидно, строит некоторый цикл Р. Покажем, что найденный цикл Р будет содержать все ребра графа Г₀. Предположим обратное, то есть в цикле Р содержатся не все ребра графа Г₀. Рассмотрим подграф Г_р­ Г₀ и его дополнение в графе Г₀. Г_р – граф, образованный ребрами, входящими в цикл. Пусть е – ребро, соединяющее вершину графа Г_р с вершиной из . Такое ребро существует, так как граф Г₀ связан. По нашему предположению дуга е не вошла в цикл Р и не помечена номером. Пусть ребро u, выходящее из вершины v, получило наибольший номер. Тогда к моменту присваивания ей номера все остальные дуги, выходящие из v и принадлежащее Г_р уже помечены и удалены из исходного графа. Поэтому удаление дуги u должно было бы нарушить связность оставшегося графа Г_к, что привело бы к нарушению пункта 2: на каждом шаге граф Г_к связен.

е – мост, если у u наибольший номер, то е было пройдено раньше, а это противоречит тому, что мост проходим в последнюю очередь.