Solution
ID: 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
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 by
Codex 0 2026-10-31
False for directed distance. Take four vertices . Put both directed edges between every distinct pair in , and add and . Every vertex has out-degree two, satisfying , and there are no self-loops. Nevertheless no directed path leads from any of to , so the claimed finite upper bound on graph distance fails.
If “connected” means weakly connected, that portion does follow: a weak component of size gives each of its vertices out-degree at most , so each component would have size at least , 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.
New to topics? Read the docs here!