Does the Cayley digraph $C$= [(12)(34),(123):$A_4$] have a Hamiltonian Circuit?

Question

This is a problem I'm working on for a friend of mine. I haven't been able to solve it, or make much progress. I have drawn the digraph, and it consists of four directed cycles of three vertices all linked by the (123) generator. the four cycles are linked to each other via bidirectional edges associated with the generator (12)(34).

I've done a pretty exhaustive "brute force" search, and I think there is no hamiltonian circuit because the four cycles being directed makes it impossible not to hit the same cycle twice, but the results in the only text I own which is relevant (Lint&Wilson) haven't been useful in trying to prove there is no such circuit.

Hints strongly preferred. No answers please. The first line of a proof and an explanation of what I should think about would be ideal =)

Answer 1

Here's the digraph with the vertices belonging to the directed $3$-cycles colored the same.

I think the key point is:

• In any Hamilton cycle, a vertex of a given color is adjacent to another vertex of the same color. So, the same-colored vertices must occur together.

Now we can just check three possibilities: In a Hamilton cycle, one bidirectional edge is used to get to a pink vertex from a non-pink vertex. So, if we use $(1,2,4)\rightarrow(2,3,4)$ then we must follow: $$(1,2,4)\rightarrow(2,3,4)\rightarrow(1,2)(3,4)\rightarrow(1,3,4)\rightarrow(1,4,2)\rightarrow(1,4,3)\rightarrow(1,4)(2,3)\rightarrow(1,3)(2,4)$$ and we're back at blue too early, so we won't get a Hamilton cycle. And so on for the other two possibilities.