Эйлеровы графы.

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

Док-во: необх. Начнем движ-е по эйлерову циклу с середины произ. ребра и будем подсчитывать по ходу движ-я степени вершин. При прохождение через вершину ее степень увелич. на 2,поэтому степени всех вершин эйлерова гр-а четны. достат. (при помощи индукции).Если степень кажд. вершины четна, то граф содерж. цикл, действительно, начнем строить цепь из произв. вершины:V1→V2→… Т.к. кажд. вершина инцидентна четному числу ребер, то, попав в отличную от Vi вершину, можно продолжать движ-е по ранее не пройденному пути. Т.к. число вершин конечно,то рано или поздно в цепи повтор-ся вершина, например Vn. Часть цепи между 2-умя вхождениями Vn образ. цикл,назовем его С.Если Ссодерж. все ребра G,то С-эйлеров цикл,иначе удалим из G все ребра,образующие С и тогда граф распадается на k компонент связностей,k≥1,при этом степень кажд. вершины ост-ся четной.Поскольку она либо не меняется,либо уменьш-ся на 2,либо на число кратное двум.Пусть утверждение теоремы справ-во для любого графа с числом ребер меньшим чем у G.Тогда каждого из графов Нi можно построить эйлеров цикл так: выходим из произв.вершины С и двигаемся по ребрам,если встреч. неизолиров-ую вершину графа Нi,то следуем по эйлерову циклу Нi-ым.Потом возвращ. в С и продолж. движ-е по нему.Т.о. мы пройдем все ребра G и цепь замкнется.

Следствие.

Связ. граф явл. полуэйлеровым в нем не более 2-ух вершин имеют нечетн. степень.

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