TriplyHamiltonian edge colorings
Mark Jason Dominus recently made a blog post about the interesting observation that the regular dodecahedron can have its edges properly colored with three colors so that every two colors form a Hamiltonian cycle. Here’s another view of the same dodecahedral coloring:
Mark’s drawing is easier to recognize as the dodecahedron, but this drawing style makes clear the Hamiltonicity of one of the pairs of colors: just look at the outer cycle. As with every planar graph drawn like this as a Hamiltonian cycle plus some diagonals, the diagonals can be partitioned into two noncrossing subsets, belonging to the front and back sides of an embedding of the graph onto a dihedron. I’ve shown this by casing the crossings to show which diagonal is front and which is back at each crossing. The diagonals subdivide the front and back into the faces of the planar embedding and you can trace through the faces to check that there are 12 pentagons, six on the front and six on the back.
This property of having a triplyHamiltonian edge coloring is not special to the dodecahedron. It’s known to be true of every 3regular graph whose edge coloring is unique (up to permutation of colors). This class of graphs includes the graph of the tetrahedron (\(K_4\)) as well as the nonplanar generalized Petersen graph \(G(9,2)\).
The proof that uniquely 3edge colorable graphs must be triply Hamiltonian is easy: if not, some two colors would form a 2regular subgraph with multiple connected components, and you could get a different edge coloring by swapping the colors in one of the components. And there cannot be any other Hamiltonian cycles in these graphs, because every Hamiltonian cycle leads to a coloring like the one in the first illustration that alternates colors around the cycle and uses the third color for the diagonals. The larger generalized Petersen graphs \(G(6k+3,2)\) are still triplyHamiltonian; they have exactly three Hamiltonian cycles but do not have a unique edge coloring.^{1}
Two uniquely 3edge colorable graphs can be glued together by removing one vertex from each graph and reattaching the neighbors of the removed vertices by three new edges.
Starting from \(K_4\) and \(G(9,2)\), this produces infinitely many uniquely 3edge colorable graphs. The ones glued from only copies of \(K_4\) are planar (the duals of the Apollonian networks) but the ones involving \(G(9,2)\) are nonplanar.^{2} As far as I know, all uniquely 3edge colorable graphs are generated from \(K_4\) and \(G(9,2)\) by this operation, with one exception: the twovertex threeedge multigraph, which is the identity element for the operation. If so, this would lead to a polynomial time algorithm for recognizing and coloring these graphs. The same operation also preserves triplyHamiltonian edge colorings even when they aren’t the unique 3edgecoloring of the graph.
Another operation does not preserve unique 3edgecoloring, but it does preserve triplyHamiltonian edge coloring: take any two differentlycolored edges of a single graph, subdivide them into threeedge paths, and connect the four new vertices in pairs.
For instance, depending on how you choose the two edges, you can use this operation to get from the twovertex multigraph to either the triangular prism or the nonplanar complete bipartite graph \(K_{3,3}\).
You can’t get the dodecahedron or \(G(9,2)\) by these operations (they have neither 4cycles nor 3edge cuts) but by using these operations, you can get infinitely many other triplyHamiltonian graphs. In fact, it seems difficult to find 3vertexconnected cubic graphs that are not triplyHamiltonian! So I’ll conclude by giving two families of graphs that are not triplyHamiltonian.
The first nontriplyHamiltonian family is the family of prism graphs over odd polygons: the pentagonal prism, heptagonal prism, etc. We have already seen that the first graph in this family, the triangular prism, is triplyHamiltonian, but the rest are not. They only have one Hamiltonian cycle, up to symmetries of the graph: the cycle that uses all but one edge from each of the two nonquadrilateral faces of the prism, and connects the resulting two paths by two edges of one of the quadrilaterals. But the threeedgecoloring that you get from this Hamiltonian cycle has only two colors on some of the quadrilateral faces, so those pairs of colors do not themselves form Hamiltonian cycles.
The second nontriplyHamiltonian family is the family of planar 3regular bipartite graphs (including the cube, the rest of the prisms, and a lot more graphs besides). To see this, let \(G\) be a planar 3regular bipartite graph. If \(G\) is not Hamiltonian then obviously it is not triplyHamiltonian; otherwise, draw \(G\) as in the first illustration, with two colors alternating around an outer Hamiltonian cycle and the third color used for all the interior diagonals. And, as in the first illustration, partition the interior diagonals into the ones on the front and back sides of an embedding onto a dihedron. These diagonals partition the front and back sides into the faces of a planar embedding.
The number of front faces is one more than the number of front diagonals, and the number of back faces is one more than the number of back diagonals, so the total number of faces is more than the total number of diagonals. There are two kinds of vertex in each face: “inner vertices” incident to a diagonal edge of the face, and “outer vertices” incident to two edges of the outer Hamiltonian cycle that both belong to the face. Every face has an even number of inner vertices, so if the graph is to be bipartite every face must also have an even number of outer vertices (zero or at least two). Because there are two outer vertices per diagonal (on the other side of the dihedron from the diagonal) but more faces than diagonals, there must be at least one face with no outer vertices. But then this face has edges that alternate between only two colors, and these two colors cannot form a Hamiltonian cycle. Since we can apply this argument to every threeedgecoloring of a bipartite planar graph in which two of the colors form a Hamiltonian cycle, this proves that no planar bipartite graph can be triply Hamiltonian.
On the other hand, planarity is essential to this argument, as we have already seen an example of a triplyHamiltonian bipartite graph, the graph \(K_{3,3}\). By gluing copies of \(K_{3,3}\) together, we can get arbitrarily large triplyHamiltonian bipartite graphs, all of which must be nonplanar.

Thomason, Andrew (1982), “Cubic graphs with three Hamiltonian cycles are not always uniquely edge colorable”, J. Graph Th. 6 (2): 219–221. ↩

belcastro, sarahmarie, and Haas, Ruth (2015), “Trianglefree uniquely 3edge colorable cubic graphs”, Contributions to Discrete Mathematics 10 (2): 39–44. ↩
(\(\mathbb{M}\), G+)