Michael’s last post on cubic vertex-transitive graphs mentioned, almost in passing, that every graph in the new catalogue has been checked to see whether it contains a Hamilton cycle – in other words, a cycle passing through each vertex exactly once.

The reason to check this particular property is a very famous and very perplexing conjecture:

Conjecture: Every connected vertex-transitive graph, other than $K_2$, the Petersen graph $P$, the Coxeter graph $C$ and the two graphs obtained from $P$ and $C$ by replacing each vertex with a triangle, has a Hamilton cycle.

Naturally enough, the five graphs in the statement are the only vertex-transitive graphs that are known to not have Hamilton cycles. Of these, $K_2$ can be viewed as a triviality and ignored, but none of the others are Cayley graphs. So a related conjecture is often expressed as follows:

Conjecture: Every connected Cayley graph has a Hamilton cycle.

I don’t know who actually first stated these as conjectures – certainly Lovász made a much weaker conjecture about transitive graphs having Hamilton paths, but I’m not sure whether he made these stronger conjectures.