Лемма : В любом графе число вершин нечётной степени чётно.
Доказательство: По теореме 1 сумма степеней всех вершин число чётное. Сумма степеней вершин чётной степени чётна, значит, сумма степеней вершин нечётной степени также чётна, значит, их чётное число.
Пусть G(p) – множество всех графов с р вершинами, а Е(р) – множество эйлеровых графов с р вершинами.
Теорема 6: Эйлеровых графов почти нет, то есть
lim 
Доказательство: Пусть E/ (р) – множество графов с р вершинами и чётными степенями. Тогда по теореме1 Е(р)ÌЕ/(p) и |Е(р)|£|Е/(p)|.В любом графе число вершин нечётной степени чётно, следовательно, любой граф из Е/(p) можно получить из некоторого графа G(p-1), если добавить новую вершину и соединить её со всеми старыми вершинами нечётной степени. Следовательно, |Е/(p)| £|G(p-1)|. Но |G(p)|=2C(p, 2). Заметим, что
С(k,2)-C(k-1,2)=
= 
Далее имеем:
|Е(р)|£|Е/(p)| £|G(p-1)| = 2C( p-1,2) =2C(p,2)-(p-1) = |G(p)|2-(p-1)
и
, откуда lim 
. [3]
Алгоритм построения эйлеровой цепи в данном эйлеровом графе.
Этот метод известен под названием алгоритма Флёри.
Теорема 7: Пусть G – эйлеров граф, тогда следующая процедура всегда возможна и приводит к эйлеровой цепи графа G. Выходя из произвольной вершины и, идём по рёбрам графа произвольным образом, соблюдая лишь следующие правила:
стираем рёбра по мере их прохождения и стираем также изолированные вершины, которые при этом образуются;
На каждом этапе идём по мосту только тогда, когда нет других возможностей.
Доказательство: Покажем сначала, что указанная процедура может быть выполнена на каждом этапе. Предположим, что мы достигли некоторой вершины V; тогда если V¹U, то оставшийся подграф H связен и содержит ровно две вершины нечётной степени, а именно U и V. Согласно теореме 3 и определению полуэйлерова графа, граф H содержит полуэйлерову цепь P из V в U. Поскольку удаление первого ребра цепи Р не нарушает связности графа Н, то описанное в теореме построение возможно на каждом этапе. Если же V=U, то доказательство остаётся тем же самым до тех пор, пока есть ещё рёбра, инцидентные вершине U.
Осталось только показать, что данная процедура всегда приводит к полной эйлеровой цепи. Но это очевидно, так как в G не может быть рёбер, оставшихся не пройденными после использования последнего ребра, инцидентного U. В противном случае удаление некоторого ребра, смежного одному из оставшихся, привело бы к несвязному графу, что противоречит условию 2).[5]
Заключение
В данной работе были рассмотрены основные понятия теории графов, их виды. Большое внимание уделили вопросу существования в них эйлеровых цепей и циклов, рассмотрели ряд теорем и свойств. Описали алгоритм нахождения эйлерова цикла в произвольном графе, а в практической части показали его применение на конкретных примерах.
Известно, что эйлеровы графы получили широкое распространение и популярность благодаря тому, что многие головоломки и задачи можно решить с использованием знаний теории графов. Частные примеры таких головоломок и сюжетных задач были приведены в практической части. Задачи на отыскание путей через лабиринты, близкие к задачам на эйлеровы графы, находят применение в современной психологии и при конструировании вычислительных машин. Также с практической точки зрения, сейчас графы применяют во многих других областях науки таких как: программирование, физика, химия, биология, экономика и т.д.
Литература
1. Андерсон, Джеймс А. Дискретная математика и комбинаторика: пер. с англ. – М.: Издательский дом «Вильямс», 2003. – 960с.
2. Березина Л. Ю. Графы и их применение. – М.: Просвещение, 1979.
3. Новиков С.А. Дискретная математика для программистов – СПб.: Питер, 2001. – 304с.
4. Оре о. Графы и их применение. – М.: Мир,1973.
5. Уилсон Р. Введение в теорию графов. – М.: Мир, 1977.
6. Харари Ф. Теория графов. – М.: Мир, 1973.