The treedepth 
of a graph 
is the minimum integer 
such that there exists a rooted
forest 
whose longest root-to-leaf path contains 
vertices and whose closure
contains 
as a subgraph (Nešetril and Ossona de Mendez
2006, 2012). The closure of a rooted forest is the
graph obtained by adding an edge
from each vertex to each of its ancestors.
Nešetril and Ossona de Mendez (2006) used the spelling "tree-depth." The unhyphenated spelling "treedepth" is common in modern algorithmic and structural graph theory (Czerwiński et al. 2021, Huynh et al. 2022, Hodor et al. 2026).
This graph invariant is implemented as GraphData[graph, "TreeDepth"]. Note that the Wolfram Language symbol TreeDepth[tree] has a different meaning, giving the maximum level of a symbolic tree or subtree rather than the graph invariant discussed here.
The term tree depth is also used in knot theory for a quantity associated with resolving trees of links.
Hodor et al. (2026) relate treedepth to 2-treedepth in graphs excluding a fixed path
graph as an induced subgraph. For integers 
and 
, if 
has no induced path graph 
and has 2-treedepth
at most 
,
then
 |
where 
is the floor
function. Examples attain at least half this upper bound. For graphs
with no induced 
,
treedepth equals 2-treedepth.
