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$:
- 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.
- 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$.)
- 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]$.
- 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]$.
- Theorem 22.7 then implies that the interval $[d[v], f[v]]$ is contained entirely within the interval $[d[u], f[u]]$.$^{\dagger\dagger}$
- 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.)
