Эйлеровость графов

Эйлеров путь

Путь $p$ $u_0 -\gt u_0u_1 -\gt u_1 -\gt u_1u_2 -\gt ...-\gt u_(k-1)u_k -\gt u_k$ в графе $G = (V, E)$
называется Эйлеровым, если содержит все ребра $G$, причем каждое - только один раз.

Эйлеров цикл

Цикл $p$ $u_0 -\gt u_0u_1 -\gt u_1 -\gt u_1u_2 -\gt ...-\gt u_ku_0-\gt u_0$ в графе $G = (V, E)$
называется Эйлеровым, если содержит все ребра $G$, причем каждое - только один раз.

Эквивалентно: Эйлеровым циклом является Эйлеров путь, являющийся циклом.

Эйлеров граф

Определение

Граф $G = (V, E)$ называется Эйлеровым, если содержит Эйлеров цикл.

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

Критерий Эйлеровости

Неориентированный граф

{{Теорема|theorem {{statement Неориентированный связный граф $G = (V, E)$ является Эйлеровым тогда и только тогда, когда не содержит вершин нечетной степени.
}} {{proof Достаточность:
Рассмотрим Эйлеров цикл $p$ в $G$.
Каждое вхождение вершины в цикл(кроме первого и последнего вхождения начальной вершины) добавляет 2 к ее степени.
Для начальной вершины ее первое и последнее вхождение также суммарно добавляют 2 к ее степени.

Необходимость:
Докажем утверждение по индукции.
База - лес из $N$ деревьев, каждое из 1 вершины.
Переход:
Рассмотри граф, в котором степени всех вершин четные.
В нем найдется простой цикл, т.к. иначе граф является лесом $-\gt$ в нем есть хотя бы два листа, что противоречит четности степеней всех вершин.
Рассмотрим цикл $c$ такой, что при удалении его ребер не образуется компонент связности размера больше 1.
Такой всегда существует, т.к. граф компонент двусвязности произвольного связного графа является деревом, а т.к. все вершины $G$

Рассмотрим вершину $u$ со степенью больше 2. После удаления цикла $c$ из графа степени всех вершин останутся четными,
при этом количество ребер в графе уменьшится. Для $G - c$, по предположению индукции, существует эйлеров цикл $e$.
Тогда в $G$ тоже существует Эйлеров обход - сначала обойти цикл с, начиная с вершины $u$, затем обойти $e$.
}}

Следствие
Неориентированный связный граф $G = (V, E)$ является полуэйлеровым тогда и только тогда, когда содержит ровно две вершины нечетной степени.

Ориентированный граф

Теорема
Ориентированный граф $G = (V, E)$ является Эйлеровым тогда и только тогда, входная степень любой вершины равна ее выходной степени.

Доказательство
Достаточность:
Необходимость:

Следствие
Ориентированный граф $G = (V, E)$ является полуэйлеровым тогда и только тогда, когда содержит ровно одну вершину, входная степень которой
на единицу больше выходной, и ровно одну вершину, выходная степень которой на единицу больше входной.