Вершина з нульовим ступенем заходу називається коренем дерева, вершини з нульовим ступенем результату (з яких не виходить жодна дуга) називаються кінцевими вершинами або листям.

Аналіз алгоритму Неорієнтований граф, Що складається з n вершин, буде деревомякщо він зв'язковий і містить n – 1 ребро. Запускаємо пошук у глибину із першої вершини. Якщо існує зворотне ребро, то граф має цикл і не є деревом.

В теорії графів кореневим графом називається граф, в якому одна вершина позначена, щоб відрізняти її від інших вершин. Цю спеціальну вершину називають корінням графа :454. Число кореневих графів для 1, 2, 3, … вершин дорівнює 1, 2, 6, 20, 90, 544, …

Наприклад, висота дерева на 1 більше максимальної висоти піддерев його кореня, а довжина шляху дерева з N вузлами дорівнює сумі довжин шляхів піддерев його кореня плюс N – 1.