Изменения

Пусть вершина ''v'' эйлерова графа ''G'' принадлежит любому циклу. Рассмотрим произвольную (''v, w'')-цепь ''P'' и покажем, что её можно продолжить до эйлеровой цепи. Обозначим через <mathtex>G_1</mathtex> подграф графа ''G'', полученный удалением из ''G'' всех рёбер цепи ''P''. Если ''w=v'', то все вершины подграфа <mathtex>G_1</mathtex> имеют чётную степень, если же ''w≠v'', то <mathtex>G_1</mathtex> содержит в точности две вершины нечётной степени. Пусть <mathtex>H_0</mathtex> – компонента связности графа <mathtex>G_1</mathtex> , содержащая вершину ''v''. Ясно, что вершина ''w'' принадлежит <mathtex>H_0</mathtex> . Следовательно, <mathtex>H_0</mathtex> – полуэйлеров граф, и потому в <mathtex>H_0</mathtex> существует полу-эйлерова (''w,v'')-цепь ''Q''. Очевидно, что <mathtex>H_0</mathtex> содержит все рёбра графа <mathtex>G_1</mathtex>. Предположим, что <mathtex>G_1</mathtex> содержит неодноэлементную компоненту связности ''H'', отличную от <mathtex>H_0</mathtex> . Тогда ''H'' – эйлеров граф, и потому в ''H'' содержится цикл. Этот цикл не проходит через вершину ''v'', что невозможно. Следовательно, все компоненты связности подграфа <mathtex>G_1</mathtex>, отличные от <mathtex>H_0</mathtex>, одноэлементны.<br>Таким образом, цепь ''Q'' содержит все рёбра графа <mathtex>G_1</mathtex>. Отсюда вытекает, что объединение цепей ''P'' и ''Q'' – эйлерова цепь в графе ''G'', являющаяся продолжением цепи ''P''.<br>Обратно, пусть в графе ''G'' существует цикл ''C'', не содержащий вершину ''v''. Рассмотрим подграф <mathtex>G_1</mathtex>, полученный удалением из ''G'' всех ребер цикла ''С''. Пусть ''H'' – компонента связности подграфа <mathtex>G_1</mathtex>, содержащая вершину ''v''. Легко понять, что ''H'' – эйлеров граф. Обозначим через ''P'' эйлерову цепь подграфа . Можно считать, что началом и концом цепи ''P'' является вершина ''v''. Поскольку ''v'' не принадлежит циклу ''C'', цепь ''P'' нельзя продолжить до эйлеровой цепи графа ''G''.