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:

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

Naturally enough, the five graphs in the statement are the only vertex-transitive graphs that are known to not have Hamilton cycles. Of these, 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:

: Every connected Cayley graph has a Hamilton cycle.Conjecture

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.

Continue reading “Two problems on Hamilton cycles”