= Solution
\b[False.] Use vertices $x,u,v$, edges $x\to u$, $u\to x$, $x\to v$, and start <depth-first search> at $x$, scanning $u$ before $v$. The times are
$$
\boxed{d(x)=1,\ d(u)=2,\ f(u)=3,\ d(v)=4,\ f(v)=5,\ f(x)=6.}
$$
There is a directed path $u\to x\to v$ and $d(u)<d(v)$, but $u$ and $v$ are separate children of $x$. Thus $v$ is not a descendant of $u$. The path leaves $u$ through an already gray ancestor; its later branch need not be explored inside $u$'s recursive call. This is consistent with the <DFS parenthesis property>.
\Image[/past-exam-of-the-year-1-of-the-computer-science-course-of-the-university-of-oxford/2017/algorithms-resit-dfs-counterexamples.png]
{title=DFS counterexamples distinguish reachability from tree ancestry}
{description=Left: the path from u through its ancestor x reaches a later sibling v, after u has finished. Right: root order a,u,c makes three singleton DFS trees, though u has an incoming and an outgoing edge.}
Back to article page
