Solution

ID: past-exam-of-the-year-1-of-the-computer-science-course-of-the-university-of-oxford/2013/functional-programming-design-and-analysis-of-algorithms/8/b/solution

Allow a zero-length graph path, as in Question 5. Then every vertex reaches itself, proving reflexivity. If , its definition already includes both directions of reachability, so interchanging proves symmetry.
If and , concatenate the graph paths and to obtain reachability from to . Similarly concatenate and for the reverse direction. Repeated vertices can be removed if graph paths are required to be simple. Thus , proving transitivity. Consequently
The zero-length convention matters for an isolated vertex: it is still a singleton strongly connected component.

New to topics? Read the docs here!