що граф G має Ейлером цикл. Граф є зв'язковим, так як кожна вершина належить циклу. Для всякої вершини v графа G щоразу, коли Ейлером цикл проходить через v , він вносить 2 в ступінь v . Тому ступінь v парна.
Зворотно, потрібно показати, що кожен зв'язний граф, у якого ступеня вершин парні, має Ейлером цикл. Доведемо цю теорему, використовуючи індукцію за кількістю вершин. Оскільки теорема тривіально справедлива при n ВЈ 3, почнемо індукцію з n = 3. Припустимо, що кожен зв'язний граф, що має менш k вершин, і всі вершини якого володіють парною ступенем, містить Ейлером цикл. Нехай G - зв'язний граф, містить k вершин, ступеня яких парні. Припустимо, що v 1 і v 2 - вершини графа G. Оскільки граф G - зв'язний, існує шлях з v 1 у v 2 . Оскільки ступінь v 2 - парна, існує невикористане ребро, по якому можна продовжити шлях. Оскільки граф кінцевий, то шлях, зрештою, повинен повернутися в v 1 , і Ейлером цикл З 1 можна вважати побудованим. Якщо С 1 є ейлеровим циклом для G, тоді доказ закінчено. Якщо ні, то нехай G / - підграф графа G, отриманий видаленням всіх ребер, що належать З 1 . Оскільки З 1 містить парне число ребер, інцидентних кожній вершині, кожна вершина подграфа G / має парну ступінь.
Нехай e - ребро графа G /, нехай G e - компонента графа G /, що містить е. Оскільки G / має менш, ніж k, вершин, і у кожної вершини графа G / парна ступінь, граф G / має Ейлером цикл. Нехай З 2 . Далі у С 1 і С 2 є загальна вершина, припустимо, а. Тепер можна продовжити ейлерів цикл, починаючи його в а, пройти З 1 , повернутися в а, потім пройти З 2 і повернутися в а. Якщо новий Ейлером цикл не є ейлеровим циклом для G, продовжуємо використовувати цей процес, розширюючи наш Ейлером цикл, поки, до кінці кінців, не отримаємо Ейлером цикл для G. [1]
З теореми 1 випливає, що якщо в зв'язковому графі G немає вершин з непарними ступенями, то в G є замкнута ланцюг, що містить всі вершини і всі ребра графа G. Аналогічний результат справедливий для зв'язкових графів, що мають деяке число вершин з непарними ступенями.
Слідство 1 (а): Нехай G- зв'язний граф, в якому 2n вершин мають непарні ступеня, n> 1. Тоді безліч ребер графа G можна розбити на n відкритих ланцюгів.
Слідство 1 (б): Нехай G- зв'язний граф, в якому дві вершини мають непарні ступеня. Тоді в G є відкрита ланцюг, що містить всі вершини і всі ребра графа G (і що починається в одній з вершин з непарної ступенем, а кончающаяся в іншій). [6]
ейлерова шляхом у графі називається шлях, що містить всі ребра графа. Ейлером шлях називається власним, як...
