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:**

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:Theorem 22.7 (Parenthesis theorem)

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.

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]$ .Corollary 22.8 (Nesting of descendants’ intervals)

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,
$ ^\dagger$ Therefore, $ d[u] < d[v] < f[w] \leq f[u]$ .but before $ w$ is finished.$ ^{\dagger\dagger}$Theorem 22.7 then implies that the interval $ [d[v], f[v]]$ is contained entirely within the interval $ [d[u], f[u]]$ .$ ^\ddagger$ ■By Corollary 22.8, $ v$ must after all be a descendant of $ u$ .

$ \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.)