# 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?

• This question will get more attention on cs.stackexchange.com. So it might be a good idea to ask it there. Commented Jun 10, 2022 at 12:18
• What is your final question? Did you mean "How do we know that such a w exists?" Commented Jun 10, 2022 at 12:31
• @ChaitanyaChavali yes! Commented Jun 10, 2022 at 12:32

The assumption in proving the second part is that there exists a path from $$u$$ to $$v$$ in which all the vertices are white(and that $$v$$ is not a descendant of u in the DFS forest).

Let that path be $$$$

$$w=\begin{cases} w_p &\quad\text{if }p>0\\ u &\quad\text{if }p=0\\ \end{cases}$$

There can be multiple, say $$n_1$$, paths from $$u$$ to $$v$$. Out of them only $$n_2$$ paths($$n_2 \leq n_1$$) may be containing all white vertices. Out of those $$n_2$$ select any one path and use it for your proof. You can select any such path. The proof would still be valid. In each of those $$n_2$$ paths, there may be a different predecessor to $$v$$. We select one of those paths and we call the predecessor in that path as $$w$$.

• why we know $w$ in <w1, w2,..., wp> path? Can it in another path? If we explain that wp is descendant of u, and w is predecessor of v, so that v is descendant of u is obvious. I think the proof need not include theorem 22.7 and corollary 22.8. Commented Jun 10, 2022 at 12:41
• There can be multiple, say $n_1$, paths from $u$ to $v$. Out of them only $n_2$ paths($n_2 \leq n_1$) may be containing all white vertices. Out of those $n_2$ select any one path and use it for your proof. You can select any such path. The proof would still be valid. In every such path out of $n_2$ there is a predecessor to $v$. We select one path and we call the predecessor in that path as $w$. Commented Jun 10, 2022 at 12:46
• @minhquýlê It might look obvious to us, but that doesn't mean that we have proved that implication. If w is a descendant of u and w is the predecessor of v, it does not directly follow that v is a descendant of u. Please understand that there is a difference in the term descendant and predecessor. Firstly, simply saying that w is the predecessor of v makes no sense. Predecessor in what? Commented Jun 10, 2022 at 12:57
• If we knew that v is a descendant of w in the DFS forest, then what you are saying is right. But when we say that w is a predecessor of v, we are saying that w comes just before v in some path containing all white vertices. Being a predecessor in some path does not mean that it is also the ancestor in the DFS forest. Commented Jun 10, 2022 at 12:57
• Yes. Because by the time $w.d$, $v$ is still white and there is an edge from $w$ to $v$, it has to be discovered before $w.f$ Commented Jun 11, 2022 at 11:36