Изменения

Обратно, пусть в графе <tex>G</tex> существует цикл <tex>C</tex>, не содержащий вершину <tex>v</tex>. Рассмотрим подграф <tex>G_1</tex>, полученный удалением из <tex>G</tex> всех рёбер цикла <tex>C</tex>. Пусть <tex>H</tex> — компонента связности подграфа <tex>G_1</tex>, содержащая вершину <tex>v</tex>. Легко понять, что <tex>H</tex> — эйлеров граф. Обозначим через <tex>P</tex> эйлеров цикл подграфа. Можно считать, что началом и концом цикла <tex>P</tex> является вершина <tex>v</tex>. Поскольку <tex>v</tex> не принадлежит циклу <tex>C</tex>, цепь <tex>P</tex> нельзя продолжить до эйлерового цикла графа <tex>G</tex>.

}}

'''Источники:''' <br>

[[Категория: Алгоритмы и структуры данных]]

[[Категория: Обходы графов]]