Основная идея определения глубины дерева графа в теории графов заключается в том, что глубина дерева измеряет, насколько граф далёк от звезды. 1

Глубину дерева графа можно определить несколькими способами, например:

• Как минимальную высоту леса, где любое ребро графа соединяет пару вершин, связанных отношением «предок-потомок». 13
• Как размер наибольшей клики в тривиально совершенном суперграфе графа. 13
• С использованием раскраски графов, где глубина дерева — это минимальный размер цветов, необходимых для центрированной раскраски графа. 1
• В терминах игры «полицейские-грабители», где глубина дерева графа определяет минимальное число фишек, необходимых для гарантированного выигрыша. 13