Past exam of the year 1 of the computer science course of the University of Oxford / 2018 / Functional programming, design and analysis of algorithms / 7 / b

False. Take two vertices $u,v$ with both directed edges, and start depth-first search at $v$. The timestamps are $d[v]=1$, $d[u]=2$, $f[u]=3$, $f[v]=4$. There is an edge, hence a directed path, from $u$ to $v$, but $f[u]<f[v]$. Reaching a gray ancestor does not make the ancestor finish first.

False. Use only the directed edge $u\to v$, but choose $v$ first in the outer loop of depth-first search. It finishes before a second discovery tree starts at $u$: $d[v]=1$, $f[v]=2$, $d[u]=3$, $f[u]=4$. The edge supplies the required directed path and $f[u]>f[v]$, yet $d[u]>d[v]$. A path to an already black vertex need not put the two vertices into one discovery tree.

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$. ThenThe 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.

False for directed distance. Take four vertices $a,b,c,d$. Put both directed edges between every distinct pair in $\{a,b,c\}$, and add $d\to a$ and $d\to b$. Every vertex has out-degree two, satisfying $|V|/2$, and there are no self-loops. Nevertheless no directed path leads from any of $a,b,c$ to $d$, so the claimed finite upper bound on graph distance fails.

If “connected” means weakly connected, that portion does follow: a weak component of size $m$ gives each of its vertices out-degree at most $m-1$, so each component would have size at least $|V|/2+1$, making two components impossible. It does not imply a strongly connected directed graph. Thus either the strong-connectivity interpretation fails outright or the weak interpretation leaves the distance assertion false; the complete claim is false in either case.