Past exam of the year 1 of the computer science course of the University of Oxford / 2017 / Functional programming, design and analysis of algorithms (resit) / 7 / c / i / Solution

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 areThere 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.