Discrete Mathsfor Engineers

4. Structural Properties & Discovery Times

Depth-First Search is more than a traversal rule. Its timestamps encode a hidden structure in the graph exploration.

In this part, we study the formal properties of discovery times, finish times, and the interval structure generated by recursion.

4.1 Discovery and Finish Times

During DFS, every vertex u receives two timestamps:

• d[u] — the moment u is first discovered
• f[u] — the moment the exploration of u is completed

These times satisfy:

for every vertex u, because a vertex must be discovered before it can be finished.

4.2 The Interval View

Each vertex defines a time interval:

This interval represents the full active lifetime of u in the recursion.

The key structural fact is that DFS intervals are not arbitrary: they are either nested or disjoint.

4.3 Parenthesis Theorem

For any two vertices u and v, exactly one of the following holds:

• The intervals [d[u], f[u]] and [d[v], f[v]] are disjoint
• [d[u], f[u]] is fully contained in [d[v], f[v]]
• [d[v], f[v]] is fully contained in [d[u], f[u]]

4.4 Nesting Example

Suppose DFS discovers u, then from u discovers v.

Then the timestamps must satisfy:

So the interval of v is nested inside the interval of u.

4.5 Ancestor–Descendant Criterion

In a DFS tree, vertex u is an ancestor of v if and only if:

Equivalently, the interval of v is properly nested inside the interval of u.

This gives DFS a powerful structural test: ancestry can be read directly from timestamps.

4.6 Disjoint Intervals and Separate Branches

If two vertices lie in different DFS branches, or in different DFS trees of the forest, their intervals are disjoint.

So DFS timestamps separate the graph into nested recursive regions.

4.7 White-Path Intuition

A central theorem in DFS theory states: a vertex v becomes a descendant of u in the DFS forest if and only if, at the moment u is discovered, there exists a path from u to v consisting entirely of WHITE vertices.

This theorem helps justify why DFS trees encode reachability structure in such a precise way.

4.8 Why These Properties Matter

Discovery and finish times are not decorative metadata. They are the reason DFS supports:

• edge classification
• cycle detection
• topological sorting
• strongly connected components

4.9 Mini Summary

• Every vertex gets a discovery time and a finish time.
• These define intervals [d[u], f[u]].
• DFS intervals are either nested or disjoint.
• Nesting characterizes ancestry in the DFS forest.
• This structure will drive all advanced DFS applications.