the DFS tree
Depth-first search explores like someone determined to follow every corridor to its dead end before turning back: from the current vertex it dives down an unexplored edge, then dives again from there, plunging deeper and deeper until it hits a vertex with no unexplored neighbours, at which point it backtracks one step and tries the next corridor. If you keep only the edges DFS used to discover new vertices, you get a tree rooted at the start — the DFS tree — and it captures the deep, snaking shape of the search.
Mechanically, DFS uses a stack, usually the call stack of recursion. Visiting u: mark u, then for each neighbour v, if v is unvisited, record the edge u->v as a tree edge and recurse into v; when the recursion returns, continue with u's next neighbour. A clean way to read the tree is with two timestamps per vertex: a discovery time when you first enter it and a finish time when you leave it for good. These obey a nesting (parenthesis) structure: for any two vertices, their intervals [discovery, finish] are either fully nested one inside the other or completely disjoint — never partially overlapping. That nesting is the precise fingerprint of ancestor-descendant relationships: u is an ancestor of v in the DFS tree exactly when v's interval sits strictly inside u's. This single fact is the engine behind topological sort, strongly connected components, articulation points, and bridges.
The DFS tree matters because the way the original graph's edges relate to this tree reveals deep structure: edges that go from a vertex to one of its own tree-ancestors (back edges) expose cycles, and in directed graphs the finish-time order gives a valid topological sort of a DAG. It runs in O(n + m) on an adjacency list. The honest caveat: the DFS tree is not unique — change which neighbour you explore first, or which vertex you start from, and you get a different tree. What is robust is the parenthesis nesting and the edge-type classification it induces; those, not the exact tree shape, are what the downstream algorithms rely on.
Vertices a,b,c,d with edges a-b, b-c, c-a, c-d. DFS from a (exploring b before others): enter a(1), enter b(2), enter c(3), see edge c-a back to ancestor a (a back edge, a cycle!), enter d(4), finish d(5), finish c(6), finish b(7), finish a(8). Tree edges: a->b->c->d. The nesting [a:1,8] contains [b:2,7] contains [c:3,6] contains [d:4,5].
Discovery/finish times nest like balanced parentheses; v sits inside u exactly when u is v's ancestor.
The DFS tree is order-dependent and non-unique, but the parenthesis nesting of discovery/finish times always holds — and that nesting, not the particular tree, is what powers topological sort, SCCs, and articulation points.