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 , the Petersen graph , the Coxeter graph and the two graphs obtained from and 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, 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.
As Cayley graphs are so intimately related to groups, the second problem can be — and has been — attacked by focussing on one family of groups or another, and in this way a considerable number of infinite families of groups are known to produce only Hamiltonian connected Cayley graphs. Dave Morris (né Witte, assuming né is the masculine of née), who visited us last year, is responsible for several of these and gave us an entertaining talk about the problem.
The class of cubic vertex-transitive graphs is of particular interest because obviously fewer edges makes for fewer cycles so, if there is a counterexample, then looking among cubic graphs is the obvious place to start. Interestingly though, as far as I know, it has not actually been shown that the truth of either of the two conjectures can be reduced to solving them for cubic graphs. (In other words, while it seems unlikely, there might be a 4-regular counterexample or a -regular counterexample, but no 3-regular one.)
Anyway, we now know that for cubic vertex-transitive graphs, both conjectures are true up to 1280 vertices. The conjectures are interesting because, other than our inability to find counterexamples, there seems no particular reason to believe they are true. There doesn’t seem to be any convincing qualitative argument for why vertex-transitivity should be correlated with Hamiltonicity, and the need for a proof to somehow involve both and and the graphs derived from them implies that proving the first conjecture might be quite intricate.
But suppose that someone comes along with a cubic vertex-transitive graph on, say, a million vertices. If it is not Hamiltonian, how would you ever show it? Showing that a graph is Hamiltonian is usually done by heuristically finding a Hamilton cycle, but I suspect that the heuristics for cubic vertex-transitive graphs work well only because these graphs have lots of Hamilton cycles. (I haven’t actually checked this numerically yet.) To prove that a graph doesn’t have a Hamilton cycle either needs an exhaustive computer search, or to use some sort of clever indirect argument or trick. In complexity theory terms, HAMILTONIAN GRAPH is a problem in NP but not (known to be) in co-NP and this is one problem where it may really bite.
The second problem I wanted to discuss on Hamilton cycles is also about regular graphs, but in this case 4-regular graphs with no requirement for vertex-transitivity, and it is usually known as Sheehan’s Conjecture.
Conjecture (Sheehan): Every 4-regular graph with at least one Hamilton cycle has at least two.
One assumes this was inspired by the famous result that every edge in a cubic graph has an even number of Hamilton cycles through it, for which there is a beautiful parity-based proof, and so a cubic graph cannot have just one Hamilton cycle.
The result for cubic graphs works because, ultimately, it can be used to start with one Hamilton cycle and transform it into a different one. So why can’t a similar result be proved for quartic graphs?
Looking at computational data suggests that there are actually lots and lots of Hamilton cycles in quartic graphs (or zero). In fact, the smallest non-zero number of Hamilton cycles in the quartic graphs on 5, 6, 7, 8, 9, 10, 11, 12, 13, 14 and 15 vertices is 12, 16, 23, 29, 36, 36, 48, 60, 72, 72 and 72 respectively. So while there seem to be plenty of “second Hamilton cycles”, at the moment they just appear to be “there by accident” rather than being forced to be there by the existence of the first one.
Of course, this problem has attracted lots of attention – in particular Thomassen proved that a 300-regular graph with a Hamilton cycle has a second one, and the 300 has been successively reduced and is now down, I believe, to 22.