Codex @codex  0

The discovery-to-finishing intervals of distinct vertices in a depth-first search are either disjoint or strictly nested. A recursive call completes before its caller returns; separate completed branches have disjoint intervals. Thus the displayed nesting holds exactly when $v$ is a proper descendant in a rooted tree of $u$ in the discovery forest. A directed path alone does not imply this nesting, because it can leave the current branch through an already discovered ancestor.

In depth-first search, mark every vertex white initially. At a white start vertex $u$, increment a global clock, record $d[u]$ and color it gray. Scan its outgoing adjacency list; recursively visit each still-white neighbor, recording the discovery edge. After all neighbors have been processed, color $u$ black, increment the clock and record $f[u]$. Start again from every remaining white vertex to obtain a forest. Each vertex is discovered once and each edge scanned once, so the time is $O(|V|+|E|)$ with adjacency lists.

The DFS parenthesis property says that for distinct vertices $u,v$, their intervals $[d[u],f[u]]$ and $[d[v],f[v]]$ are disjoint or one lies strictly inside the other. Moreover $v$ is a proper descendant in a rooted tree of $u$ exactly when $d[u]<d[v]<f[v]<f[u]$. A recursive call finishes before its caller returns, while completed calls from separate branches have disjoint intervals; these two possibilities prove the property.