= Solution
\b[False.] Let the <directed edges> be $r\to u$, $u\to r$, and $r\to v$. Start <depth-first search> at $r$ and explore its neighbor $u$ before $v$. Then
$$
d[r]=1,\quad d[u]=2,\quad f[u]=3,\quad d[v]=4,\quad f[v]=5,\quad f[r]=6.
$$
The <directed path> $u\to r\to v$ exists and $d[u]<d[v]$, but $u$ and $v$ are siblings in the discovery <tree>. An existing path may leave the current recursive branch via a gray ancestor and only later enter a different branch. The usual white-path condition would need all vertices of a suitable path to be white when $u$ is discovered; that condition is absent here.
\Image[/past-exam-of-the-year-1-of-the-computer-science-course-of-the-university-of-oxford/2018/functional-programming-design-and-analysis-of-algorithms-dfs-branch.png]
{title=A directed path crosses from an earlier DFS branch to a later branch through the root; node labels give discovery and finishing times}
Back to article page
