Page 67 - 4496

цикл. Доказ проведемо індукцією по числу вершин. У
випадку, коли у зв'язному графі всього 2 вершини й обидві
вони мають парний ступінь (у цьому випадку маємо
мультграф, один із яких зображений на рис. 3), ясно, що в
цьому випадку є Ейлеровий цикл (при будь-якому парному
степені цих двох вершин).

Рисунок 3.3 - Мультиграф

Припустимо, що наше твердження вірне для всіх
зв'язаних графів, число вершин у яких менше п, і доведемо
його для графа, що має п вершин.
Помітимо, що за лемою 1 у цьому графі є контур
(ступінь всіх вершин більше або дорівнює 2. Якщо цей контур
містить всі ребра, то цей контур сам є Ейлеровим циклом (а
граф Ейлеровим). Видалимо всі ці ребра із графа й ті
вершини, які після видалення ребер стали мати нульовий
ступінь. Тоді одержимо новий граф (який може бути
незв'язаним), але в цьому новому графі всі вершини
обов'язково мають парний ступінь (тому що при видаленні
ребер контуру ступінь кожної вершини, що входить у цей
контур, зменшується на 2.
Новий граф розпадається на “компоненти з’вязності”,
кожна з яких повинна мати загальну вершину з вилученим
контуром (інакше первісний граф не б увби зв'язаним),
степеня всіх вершин кожного компонента зв’язності парні й
число вершин у ній менше п, тобто за індукційним
припущенням цей компонент має Ейлеровий цикл. Тепер
можемо побудувати Ейлеровий цикл у даному графі в такий

64