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

Allow a zero-length graph path, as in Question 5. Then every vertex $a$ reaches itself, proving reflexivity. If $a\equiv b$, its definition already includes both directions of reachability, so interchanging $a,b$ proves symmetry.

If $a\equiv b$ and $b\equiv c$, concatenate the graph paths $a\to b$ and $b\to c$ to obtain reachability from $a$ to $c$. Similarly concatenate $c\to b$ and $b\to a$ for the reverse direction. Repeated vertices can be removed if graph paths are required to be simple. Thus $a\equiv c$, proving transitivity. ConsequentlyThe zero-length convention matters for an isolated vertex: it is still a singleton strongly connected component.