First of all, let me give the correct attribution to this algorithm: Cook and McKenzie, Problems complete for deterministic logarithmic space.
The setup of Cook and McKenzie is that you are given an undirected graph in which the edges incident to a vertex $v$ are ordered (cyclically), and given one of them it is possible to find the next one in the order.
Consider now the following algorithm, for an vertex $v$ and an incident edge $e$:
- Set $v_0 = v$ and $e_0 = e$.
- Let $e'$ be the edge following $e$ in the cyclic order of $v$.
- Let $v'$ be the other endpoint of $e'$.
- Replace $v,e$ by $v',e'$.
- Until $v = v_0$.
- If $e \neq e_0$, return "cyclic", otherwise return "don't know".
We now have two claims:
- If $G$ is acyclic then the algorithm returns "don't know" whatever $v,e$ we start with.
- If $G$ is cyclic then there is a choice of $v,e$ for which the algorithm returns "cyclic".
To see the first claim, suppose that $G$ is acyclic, and let $v,e$ be given. Consider the connected component containing $v$. If we remove $e$ then it breaks into two connected components $C_1,C_2$, the first containing $v$, the other not containing $v$. At the first step of the algorithm, it moves to $C_2$. The only way to return to $C_1$ is via the edge $e$, and when that happens, the algorithm will return "don't know".
To see the second claim, suppose that $G$ contains some cycle $v_1,\ldots,v_\ell$, and suppose for the sake of contradiction that whenever running the algorithm with $v,e$ it outputs "don't know". Let us run the algorithm with $v=v_1$ and $e=(v_1,v_2)$. Let the edges incident to $v_2$ be $e,e_1,\ldots,e_t$. According to the assumption, the algorithm will take the edge $e_1$, get back to $v_2$ via $e_1$, traverse $e_2$, get back to $v_2$ via $e_2$, and so on. In particular, it will reach $(v_2,v_3)$ before reaching $e$. By assumption, the only way to go back to $v_1$ is via $e$, and so the algorithm will reach $v_3$ before it goes back to $v_1$.
Let the edges incident to $v_3$ be $(v_3,v_2),e'_1,\ldots,e'_s$. As before, the walk will traverse $e'_1$, go back to $v_3$ via $e'_1$, traverse $e'_2$, go back to $v_3$ via $e'_2$, and so on. In particular, it will reach $(v_3,v_4)$ before reaching $(v_3,v_2)$. Now, by assumption $(v_3,v_2)$ is the only way to get back to $v_2$, which is the only way to get back to $v_1$. Therefore the algorithm will reach $(v_3,v_4)$ before it goes back to $v_1$.
Continuing in this way, we see that the algorithm will traverse $(v_4,v_5),\ldots,(v_\ell,v_1)$, and the last edge will be the first time at which it gets back to $v_1$. We reach a contradiction since $(v_\ell,v_1) \neq (v_2,v_1)$.