ершина v i и дуга e j неінцідентні.
1.7 Ейлерові графі
Означення 1.7.1. Граф, у якому знайдеться маршрут, что ПОЧИНАЄТЬСЯ и закінчується в одній вершіні, І що проходити по всех ребрах графа Рівно один раз, назівається ейлеровім графом.
Означення 1.7.2. Послідовність вершин (может буті І з повторенням), через Які проходити Шуканов маршрут , як и сам маршрут, назівається ейлеровім циклом.
Крім того, Ейлерові удалось довести и протилежних Твердження, так что граф, в якому будь-яка пара вершин зв'язана Деяк послідовністю ребер, є Ейлеровім тоді и Тільки тоді, коли ВСІ йо вершини мают парний ступінь . З тупенем вершини v назівається число ребер, інцідентніх їй .
Теорема 1.7.1 ( теорема Ейлера ). Зв язній граф G є ейлеровім тоді и Тільки тоді, коли степені всех его вершин парні.
Доведення . Необхідність. Нехай G - ейлерів граф. Ейлерів цикл цього графа, проходячи через шкірні вершину, заходити у неї по одному ребру, а виходе - по Іншому. Це означає, что Кожна вершина інцідентна парній кількості ребер ейлерового циклу, а оскількі цею цикл містіть УСІ ребра графа, то звідсі віпліває парність степенів усіх вершин графа.
Достатність . Припустиме, что степені всех вершин графа G = ( V , E ) парні. Візьмемо Деяк вершину v 1 ГЋ V и розпочнемо з неї обхід графа, КОЖЕН раз обираючи ребро, Яке раніше НЕ вікорістовувалось. Оскількі степінь кожної вершини парний и ненульовій, то...
