Спробуємо для довільного графа вказати найменше число ланцюгів та-ких, що жодні два не мають спільних ребер і всі вони повністю накривають ра-зом весь граф. Очевидно, якщо на графі є таке сімейство ланцюгів , то кожна вершина непарного степеня повинна бути або початковою, або кінцевою вер-шиною якогось ланцюга. Загальне число вершин з непарним степенем згідно з лемою про рукостискання є парним, скажімо рівним
. Таким чином, кожне сімейство ланцюгів, які накривають граф , повинно містити принаймні
лан-цюгів.
Доведемо, що існування
вершин з непарним степенем є і достатньою умовою існування ланцюгів, які накривають граф.
Теорема 2.4. На будь-якому зв’язному графі з
вершинами непарного степеня існує сімейство ланцюгів, які в сукупності містять всі ребра графа в точності один раз кожне.
Доведення. Позначимо вершини з непарними степенями
Якщо ми додамо до нашого графу ребра
то всі вершини отриманого графа будуть парними і на ньому знайдеться ойле-рів цикл
. При відкиданні доданих ребер цикл
розпадеться на
окремих ланцюгів , які містять всі ребра графа.
Граф , зображений на рисунку 2.8 має чотири вершини з непарним степе-нем
і накривається двома ланцюгами
і
Рис.2.8. Граф з непарним степенем вершин до теореми 2.4
В розважальній математиці ось уже впродовж декількох століть розгляд-даються задачі, які можна сформулювати як задачу пошуку певних маршрутів в графах, зокрема, пошуку ойлерових циклів.
Так, граф на рисунку 2.9. називається «шаблею Магомета», а ойлерів цикл необхідно побудувати за маршрутом, не відриваючи пера ручки від рисунку за одним разом ( тобто розчерком), викреслити фігуру, подану на рис.2.9.
Рис. 2.9. Ойлерів цикл в графі – «Шабля Магомета»
Більшість збірників математичних задач з розважальної математики містять задачі про лабіринти. Лабіринт складається з коридорів та їх перех-ресть. Отже , він може бути зображений графом, в якому ребра відповідають коридорам, а вершини – перехрестям.
Ойлеровим графом повинен бути і план огляду будь-якої виставки, і вздовж приміщень виставки потрібно розставити покажчики обходу таким шля-хом, щоб кожен експонат був оглянутий рівно один раз.
Рис.2.10. Застосування апарату ойлерових циклів при розв’язанні задач “маршрут виставки» [3]
Припустимо, що експонати розташовані з обох сторін шляху, який про-ходить територією виставки. Виявляється, що тоді, яким би не був відповідний граф ( або лишень він був зв’язний), можна провести відвідувача так, щоб кож-ний шлях був пройдений двічі-по одному разу в кожному напрямі (див.рис.2.10).
Теорема 2.5. В зв’язному графі існує орієнтований цикл, який проходить через ребро по одному разу в кожному з двох напрямів.
Доведення.
Сформулюємо загальне правило побудови ланцюга, який проходить взовж всіх ребер графа в точності по одному разу в кожному напрямі. Розпоч-немо з довільної вершини
і пройдемо вздовж
, відзначивши це ребро маленькою стрілкою в точці
, яка показує вибраний напрям. Потім перехо-димо послідовно до інших вершин. Одній й ті ж вершини можна відвідувати і декілька раз. Кожного разу , потрапивши в якусь вершину, ми будемо ставити на відповідному ребрі стрілку, яка вказує напрям прибуття. Крім того, потрап-ляючи в якусь вершину вперше, ми як-небудь відзначимо вхідне ребро, щоб потім його можна було відрізнити від інших.
Рис.2.11. Граф до теореми 2.5 [3]
Виходячи з вершини , ми завжди будемо обирати ще невикористаний напрям: або ребро, по якому ми зовсім не проходили, або ребро помічене стріл-кою, яка вказує на те, що ми по ньому вже були. Домовимось також, що тільки тоді , коли у нас немає вибору, ми використаємо для виходу ребро, яким впер-ше прийшли в цю вершину.
Будемо продовжувати шлях до тих пір, коли це взагалі можливо .В кож-ній вершині є однакове число можливостей для входу і для виходу. Тому рух може закінчитися лише в точці
. Залишається перевірити , що у всіх верши-нах всі ребра будуть пройдені в обох напрямах.Для точки
це ясно-всі ребра, які виходять , будуть використані, оскіль-ки в протилежному випадку ми могли б рухатися далі ; тому і всі ребра , які входять, також будуть використані, бо їх число дорівнює числу ребер, які ви-ходять. Зокрема, ребро буде пройдено в обох напрямках. Але це означає , що всі ребра , які інцидентні , також будуть пройдені в обох напрямах, бо перше ребро, яке входить в , ребро , за умовою, повинно використову-ватися для виходу лише в останню чергу. Теж саме міркування можна застосу-вати до наступного ребра 
і наступної вершини 
і так далі.Отже, в усіх вершинах , які будуть досягнуті, всі ребра виявляться прой-деними в обох напрямах. Оскільки наш граф є зв’язним, це означає, що він буде повністю обійденим.
Зауважимо, що описаний метод обходу графа може бути використаний для розв’язання задач , пов’язаних з пошуками маршрутів виходу з лабіринтів.
2.3 Приклади ойлерових графів
Нехай є кілька різних вакантних посад і група людей, які бажають їх зайняти, причому кожен із претендентів достатньо кваліфікований для кількох, але не для всіх наявних посад.
Чи можна кожному з цих людей надати одну з тих посад, які йому підло-дять?
Ми можемо знову проілюструвати цю задачу за допомогою деякого графа, що в даному випадку виглядає особливо. Як уже сказано, є певна група людей, яку ми позначимо як М і деяка множина посад, Р. Будуємо граф, проводячи ребра (м,р), що з’єднує кожну людину м з тими посадами р, які він може зайняти. На цьому графі не буде ребер, що з’єднують між собою дві вершини М чи Р, тому такий граф має вигляд, наведений на рис.2.12:
Рис.2.12. Граф для рішення задачі про призначення на посаду
Завжди знайти підходяще місце для кожного претендента ми не можемо: для цього необхідно, щоб посад було не менше ніж претендентів. Але цього недостатньо.
Нехай, наприклад, група претендентів складається з двох столярів і людини, яка може працювати і столяром і сантехніком, і для них є чотири посади: одне місце столяра і три місця сантехніка. Тоді, очевидно, один столяр залишиться без роботи, хоча в даному випадку місць більше ніж претендентів, і хоча серед претендентів є люди що можуть працювати на двох посадах.
Припустимо, що загальна кількість претендентів - N. Для виконання задачі повинна виконуватись наступна умова:
Яку б групу із k чоловік, k=1,2,...,N, ми не взяли, повинно бути принаймні k посад, кожну з яких може займати хоча б один із наших претендентів.
Наприклад, якщо один з людей є столяром, а другий - одночасно і столя-ром і сантехніка і якщо є два місця сантехніка, то наша умова виконується при k=2, але не виконується при k=1, тому вказані люди не можуть одночасно влаштуватися на роботу.
Виділену умову ми коротко назвемо умовою різноманітності.
Висновок: вищенаведена задача може використовуватись працівниками служби зайнятості для правильного розміщення працівників на посади.
Приклад 2.2. Інші формулювання
Ця задача, про встановлення на графі деякої відповідності між його вер-шинами, може мати і багато інших формулювань.
Припустимо, наприклад, що у нас є група із k хлопців і k дівчат. Дехто з них уже знайомі між собою, і виникає питання: в якому випадку можна розбити цих молодих людей не пари для танців так, щоб всі хлопці танцювали зі знайо-мими дівчатами?
Можна також змінити цю задачу: в маленькому селі є однакова кількість дорослих хлопців і дівчат; звичаєм не допускається, щоб хлопець одружувався на близькій родичці - сестрі, названій сестрі або двоюрідній сестрі. За якої умо-ви для хлопця знайдеться наречена з цього села? Знову ми можемо розв’язати цю задачу за допомогою дводольного графа - в цьому випадку його вершини будуть з’єднані ребрами лише тоді, коли відповідні люди не є родичами.