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 / iv / Solution

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.