Изменения
→Критерий эйлеровости
|statement=
Для того, чтобы граф <tex>G = (V, E) </tex> был эйлеровым необходимо чтобы:
1. Количество вершин нечетной степени не превосходило двухВсе вершины имели четную степень.
2. Все компоненты связности кроме, может быть одной, не содержали ребер.
|proof=
1. Допустим в графе количество вершин существует вершина с нечетной степени больше двухстепенью. Заметим, что при попадании в вершину и при выходе из нее мы уменьшаем ее степень на два(помечаем уже пройденые ребра), если эта вершина не является стартовой или (она же конечная для цикла). Для стартовой(конечной) вершины мы уменьшаем ее степень на один в начале обхода эйлерова цикла, и на один при завершении. Следовательно вершин с нечетной степенью быть не может быть больше двух. Наше предположение неверно.
2. Если в графе существует более одной компоненты связности с ребрами, то очевидно, что нельзя пройти по их ребрам одним путем.
