Правило Ейлера:

1. У графі, що не має вершин непарних ступенів, існує обхід всіх ребер (причому кожне ребро проходиться в точності один раз) з початком в будь-якій вершині графа.

2. У графі, що має дві і тільки дві вершини з непарними ступенями, існує обхід з початком в одній вершині з непарної ступенем і кінцем в іншій.

3. У графі, що мають більше двох вершин з непарної ступенем, такого обходу не існує.

Існує ще один вид задач, пов'язаних з подорожами уздовж графів. Мова йде про завдання, в яких потрібно відшукати шлях, що проходить через всі вершини, причому не більше одного разу через кожну. Цикл, що проходить через кожну вершину один і лише один раз, носить назву Гамільтона лінії (на честь Вільяма Роуена Гамільтона, знаменитого ірландського математика минулого століття, який першим почав вивчати такі лінії). На жаль, поки що не знайдено спільних критеріїв, за допомогою яких можна було б вирішити, чи є даний граф Гамільтона, і якщо так, то знайти на ньому всі лінії Гамільтона.

Інша стара топологічна завдання, яке особливо довго непіддавалася рішенням і розбурхувала розуми любителів головоломок, відома як

"Задача про електро-, газо- і водопостачання". У 1917 році Генрі Е. Дьюденідав їй таке формулювання. У кожний з трьох будинків, зображених на малюнку,необхідно провести газ, світло і воду.

У середині 19 ст. з'явилися роботи, в яких при вирішенні практичних завдань були отримані результати, пов'язані з теорії графів.

Так, наприклад, Г. Кирхгоф при складанні повної системи рівнянь для струмів і напруги в електричній схемі запропонував по суті представляти таку схему графом і знаходити в цьому графі остовне дерева, за допомогою яких виділяються лінійно незалежні системи контурів. А. Келі, виходячи із завдань підрахунку числа ізомерів граничних вуглеводнів, прийшов до завдань