Якщо шлях проходження вздовж кожного ребра рівно один раз, то маршрут називається шляхом Ейлера (або маршрутом Ейлера). Якщо, крім того, початкова і кінцева вершини однакові (таким чином, ви проводите вздовж кожного краю рівно один раз і закінчуєте з того місця, де почали), тоді прогулянка називається кругом Ейлера (або туром Ейлера).
Якщо мережа має рівно дві вершини непарного ступеня, тоді мережа має слід Ейлера (і тому її можна пройти). Ці дві вершини будуть початком і кінцем стежки. Якщо мережа не має вершин непарного ступеня, то мережа має схему Ейлера (тому вона є мережею Ейлера).
Теорема: Зв'язний граф містить ейлерів слід тоді і тільки тоді, коли рівно дві вершини мають непарний ступінь, а решта мають парний ступінь. Дві вершини з непарним ступенем мають бути кінцевими вершинами в сліді.
Зв’язний граф G є ейлеровим тоді і тільки тоді, коли ступінь кожної вершини G парний. Висновок цієї теореми є необхідною і достатньою умовою для напівейлерового графа: зв’язний граф є напівейлеровим тоді і тільки тоді, коли він має рівно дві вершини непарного степеня.
Для існування ейлерових слідів необхідно, щоб нуль або дві вершини мають непарний ступінь; це означає, що граф Кенігсберга не є ейлеровим. Якщо немає вершин непарного ступеня, усі ейлерові сліди є контурами.
Граф має контур Ейлера тоді і тільки тоді, коли степінь кожної вершини парний. Граф має шлях Ейлера тоді і тільки тоді, коли є щонайбільше дві вершини з непарним ступенем.