# Difficulty in understanding a portion in the proof of the $\text{“white path”}$ theorem as with in CLRS text

I was going through the $$\text{DFS}$$ section of the Introduction to Algorithms by Cormen et. al. and I faced difficulty in understanding the $$\Leftarrow$$ direction of the proof of the white path theorem. Now the theorem which is the subject of this question depends on two other theorems so I present the dependence before presenting the actual theorem and the difficulty which I face in the said.

Dependencies:

Theorem 22.7 (Parenthesis theorem) In any depth-first 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 $$[d[u], f[u]]$$ and $$[d[v], f[v]]$$ are entirely disjoint, and neither $$u$$ nor $$v$$ is a descendant of the other in the depth-first forest,

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

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

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

Theorem 22.9 (White-path theorem)

In a depth-first 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 $$d[u]$$ that the search discovers $$u$$, vertex $$v$$ can be reached from $$u$$ along a path consisting entirely of white vertices.

Proof

$$\Rightarrow$$ : Assume that $$v$$ is a descendant of $$u$$. Let $$w$$ be any vertex on the path between $$u$$ and $$v$$ in the depth-first tree, so that $$w$$ is a descendant of $$u$$. By Corollary 22.8, $$d[u] < d[w]$$, and so $$w$$ is white at time d[u].

$$\Leftarrow$$:

1. Suppose that vertex $$v$$ is reachable from $$u$$ along a path of white vertices at time $$d[u]$$, but $$v$$ does not become a descendant of $$u$$ in the depth-first tree.
2. Without loss of generality, assume that every other vertex 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$$.)
3. 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) and, by Corollary 22.8, $$f[w] \leq f[u]$$.
4. Note that $$v$$ must be discovered after $$u$$ is discovered, but before $$w$$ is finished.$$^\dagger$$ Therefore, $$d[u] < d[v] < f[w] \leq f[u]$$.
5. Theorem 22.7 then implies that the interval $$[d[v], f[v]]$$ is contained entirely within the interval $$[d[u], f[u]]$$.$$^{\dagger\dagger}$$
6. By Corollary 22.8, $$v$$ must after all be a descendant of $$u$$. $$^\ddagger$$

$$\dagger$$ : Now it is clear that since $$u$$ is the first vertex to be discovered so any other vertex (including $$v$$) is discovered after it. In point $$1$$ we assume that $$v$$ does not become the decendent of $$u$$, but by the statement that but before $$w$$ is finished I feel that this is as a result of exploring the edge $$(w,v)$$ (this exploration makes $$v$$ ultimately the descendant of $$u$$, so the proof should have ended here $$^\star$$)

$$\dagger\dagger$$ : Considering the exact statement of theorem 22.7 , I do not get which fact leads to the implication in $$5$$.

$$\ddagger$$ : The proof should have ended in the $$\star$$, but why the stretch to this line $$6$$.

Definitely I am unable to get the meaning the proof of the $$\Leftarrow$$. I hope the authors are using proof by contradiction.

(I thought of an alternate inductive prove. Let vertex $$v$$ is reachable from $$u$$ along a path of white vertices at time $$d[u]$$. We apply induction on the vertices in the white path. As a base case $$u$$ is an improper descendant of itself. Inductive hypothesis, let all vertices from $$u$$ to $$w$$ be descendants of $$u$$ , where $$w$$ is the predecessor of $$v$$ in the white path. We prove the inductive hypothesis by the exploration of the edge $$(w,v)$$. But I want to understand the proof the text.)