17
правок
Изменения
м
Нет описания правки
[[Файл:ATG_part2.jpg|200px|right]]
<tex>\Leftarrow</tex> Пусть дан эйлеров граф <tex>G</tex>, вершина <tex>v</tex> принадлежит всем его циклам.<br>
Рассмотрим произвольный путь <tex>P = (v,\leadsto w)</tex>. Пусть <tex>G_1 = G/P</tex>. Возможны 2 случая:
# Если <tex>v = w</tex>, то <tex>P</tex> {{---}} цикл, значит степени всех вершин в <tex>G_1</tex> остались четными <tex>\Rightarrow</tex> <tex>G_1</tex> {{---}} эйлеров.<br>
# Если <tex>v \neq w</tex>, то так как <tex>G</tex> эйлеров граф <tex>\exists</tex> эйлеров путь <tex>(w,\leadsto v) \in G_1</tex>.
Покажем, что в обоих случаях эйлеров обход пройдет по всем ребрам <tex>G_1</tex>.
В <tex>G</tex> <tex>\exists</tex> единственная компонента связности, содержащая ребра. При удалении <tex>P</tex> их количество не могло увеличится, иначе должен быть цикл, не содержащий <tex>v</tex>(смотри рисунок). Значит в <tex>G_1</tex> <tex>\exists</tex> единственная компонента связности содержащая ребра, причем <tex>G_1</tex> либо полуэйлеров, либо эйлеров <tex>\Rightarrow</tex> в <tex>G_1</tex> <tex>\exists</tex> эйлерова цепь <tex>Q = (w,\leadsto v)</tex> <tex>\Rightarrow</tex> <tex>P+Q</tex> эйлеров цикл в графе <tex>G</tex>.
}}
