Greg Cherlin showed that Henson’s graphs are Cayley graphs, so perhaps it is time to look again at the question:

Is Covington’s graph a Cayley graph?

Here, to start things off, is a simple fact:

Covington’s graph *G* is not a Cayley graph for the infinite cyclic group.

For suppose that it is. Then the vertices can be identified with integers, and there is a subset *S* of the natural numbers such that vertices *x* and *y* are joined if and only if |*x*−*y*| ∈ *S*. Since *G* is isomorphic to its complement, we may without loss of generality suppose that 1 ∈ *S*. Let *m* be the smallest positive integer which is not in *S*.

**Claim:** If *m* does not divide *x*, then *x* ∈ *S*.

For suppose not, and let *x* be the smallest non-multiple of *m* which is not in *S*. Note that *x* > *m*. Consider the four vertices 0, *x*, *m*, *x*−*m*. Since *x*−*m* and *x*−2*m* (or 2*m*−*x*) are in *S*, we see that {0,*x*−*m*}, {*x*−*m*,*m*} and {*m*,*x*} are edges. On the other hand, since *x* and *m* are not in *S*, {0,*x*}, {0,*m*} and {*x*−*m*,*x*} are non-edges; so these four vertices induce a path, a contradiction.

So the claim is proved.

But now the complement of *G* is disconnected, since any two vertices lying in different congruence classes (mod *m*) are joined in *G*. But this contradicts the facts that *G* is connected and isomorphic to its complement.