Every connected simple graph G has an acyclic orientation. Define a graph AO(G) whose vertices are the acyclic orientations of G and whose edges join orientations that differ by reversing the direction of a single edge. It was known previously that AO(G) is connected but not necessarily Hamiltonian. However, Squire [*] proved that the square AO(G)2 is Hamiltonian. We prove the slightly stronger result that the prism AO(G) X e is Hamiltonian.
If G is a mixed graph (some edges directed, but not necessarily all), then AO(G) can be defined as before. The graph AO(G) is again connected but we give examples showing that the prism is not necessarily Hamiltonian.