# Confuse on proof of theorem 22.9 (White-path theorem) Depth-First search (DFS) on Cormen-Leiserson-Rivest-Stein "Introduction to algorithms" book

I'm reading the DFS section of CLRS-Introduction to Algorithms, and confuse on the $$\Leftarrow$$ direction of the proof of the white-path theorem of DFS algorithm in this book.
Note that each node u in the graph has 2 timestamps: $$u.d$$ records when u is discovered and $$u.f$$ records when the search ﬁnishes examining u’s adjacency list .

Dependencies:

Theorem 22.7 (Parenthesis theorem)
In any depth-ﬁrst search of a (directed or undirected) graph $$G = (V, E)$$, for any two vertices u and v, exactly one of the following three conditions holds:

• the intervals $$[u.d, u.f]$$ and $$[v.d, v.f]$$ are entirely disjoint, and neither u nor v is a descendant of the other in the depth-ﬁrst forest,

• the interval $$[u.d, u.f]$$ is contained entirely within the interval $$[v.d, v.f]$$, and u is a descendant of v in a depth-ﬁrst tree, or

• the interval $$[v.d, v.f]$$ is contained entirely within the interval $$[u.d, u.f]$$, and v is a descendant of u in a depth-ﬁrst tree.

Corollary 22.8 (Nesting of descendants’ intervals)
Vertex v is a proper descendant of vertex u in the depth-ﬁrst forest for a (directed or undirected) graph G if and only if $$u.d < v.d < v.f < u.f$$.

Proof of theorem 22.9:

Theorem 22.9 (White-path theorem)
In a depth-ﬁrst forest of a (directed or undirected) graph $$G = (V, E)$$, vertex v is a descendant of vertex u if and only if at the time $$u.d$$ that the search discovers u, there is a path from u to v consisting entirely of white vertices.

Proof $$\Rightarrow$$: If $$v = u$$, then the path from u to v contains just vertex u, which is still white when we set the value of $$u.d$$. Now, suppose that v is a proper descendant of u in the depth-ﬁrst forest. By Corollary 22.8, $$u.d < v.d$$, and so v is white at time $$u.d$$. Since v can be any descendant of u, all vertices on the unique simple path from u to in the depth-ﬁrst forest are white at time $$u.d$$.

$$\Leftarrow$$ Suppose that there is a path of white vertices from u to v at time $$u.d$$, but v does not become a descendant of u in the depth-ﬁrst tree. Without loss of generality, assume that every vertex other than v along the path becomes a descendant of u.(Otherwise, let v be the closest vertex to u along the path that doesn’t become a descendant of u.) Let $$w$$ be the predecessor of v in the path, so that $$w$$ is a descendant of u (w and u may in fact be the same vertex). By Corollary 22.8, $$w.f \leq u.f$$ . Because v must be discovered after u is discovered, but before w is ﬁnished, we have $$u.d < v.d < w.f \leq u.f$$ . Theorem 22.7 then implies that the interval $$[v.d, v.f]$$ is contained entirely within the interval $$[u.d, u.f]$$. By Corollary 22.8, v must after all be a descendant of u.

In the proof, they let $$w$$ be the predecessor of v in the path. How do we know that such a $$w$$ exists? And if such $$w$$ exists, whether or not theorem 22.7 and corollary 22.8 are unnecessary, because i think if $$w$$ is predecessor of v, so that v is descendant of w, which directly implies that v is descendant of u?

I'm not sure what the problem is, but I will still try to answer.

The predecessor of $$v$$ in a path from $$u$$ to $$v$$ is the last vertex seen before $$v$$.

Since there exists a path from $$u$$ to $$v$$ then, unless $$v = u$$, $$v$$ has necessarily a predecessor.

More formally, if $$(u_0, u_1, …, u_k)$$ is a path of length $$k$$ from $$u = u_0$$ to $$v = u_k$$, then the predecessor of $$v$$ is $$u_{k-1}$$. It exists unless $$u = v$$.

• if w is predecessor of v in the path, so that v is w's descendant. i think it directly implies that v is descendant of u and theorem 22.7, corollary 22.8 is unnecessary Commented Jun 10, 2022 at 16:35
• @minhquýlê your question was "How do we know that such a $w$ exists?". Your comment suggests that you meant something more than just this question. Please be precise in your post in what you are asking. Commented Jun 10, 2022 at 16:44