Неорієнтований граф має цикл у тому і лише в тому випадку, коли пошук у глибину (DFS) знаходить ребро, що призводить до вже відвіданої вершини (зворотна дуга). Так само всі ребра, які алгоритм DFS виявляє, є частинами циклів.
Цикл – граф, Що складається з єдиного циклу, або, іншими словами, деякого числа вершин, з'єднаних замкнутим ланцюгом. Граф-цикл із n вершинами позначають як Cn. Число вершин Cn дорівнює числу ребер і кожна вершина має ступінь 2, тобто будь-яка вершина інцидентна рівно двом ребрам.
Ліс (або ациклічний граф) — граф без циклів. Кожна складова лісу є деревом.
Визначення 13 (Дерево). Зв'язковий граф без циклів називається дерево.