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