Доказательство. В графе и – единственные нечетные вершины в графе .

В графе и – единственные нечетные вершины в графе .

Покажем, что существует Эйлеров путь. Возможны 2 случая.

1) Вершины и соединены ребром.

Получили новый граф, путем зачеркивания единственного ребра, степени всех вершин – четные.

а)Граф не распался на 2 компоненты связности.

По предыдущей теореме, существует Эйлеров путь, добавляя назад ребра, получим: .

б)Граф распался на 2 компоненты связности. Степени всех вершин четные, значит в каждой компоненте связности существует циклический Эйлеров путь.

– в одной компоненте связности.

– в другой компоненте связности.

Тогда получаем:

2) Вершины и не соединены ребром.

Добавляем ребро, степени вершин – четные, значит, существует циклический Эйлеров путь. ()

Удаляем ребро, получаем: .

Получили Эйлеров путь.