## Trinity (Solitaire XI)

The puzzle from over a month ago is based on a curios 3-coloring of the edges of the dodecahedral graph:

Whenever you delete the edges of one color, the remaining edges form a Hamiltonian cycle. Incidentally, on the dodecahedral graph there are two different such paths, up to symmetries of the graph. The question arises whether there are more such graphs.

One such example is the Heawood graph drawn on a torus above (i.e. you identify opposite edges of the big shaded hexagon like in hexagonal astroids). There is a very symmetrical (and boring) edge coloring that colors all parallel edges the same way that is triply Hamiltonian, but there is a different one as well. You can think of this as living on the vertices of a map drawn inside a big hexagon, so that you can travel across a hexagon edge by continuing at the same position of the opposite edge. There are three types of roads, color coded, and each inhabitant of your country is issued two colored passes allowing them to travel on roads of those two colors only. Luckily, the colorings above allow each inhabitant to still travel everywhere, regardless of the passes they have been issued.

To turn this into a puzzle, we use the dual tiling by triangles, that gives us a single triangular puzzle piece (and its mirror) to place on the vertices of the graphs. For instance, below we place one triangle (with its translated copies) on three of hexagon vertices, choose another triangle elsewhere, and are tasked to complete this to a triply Hamiltonian tiling. The solution on the right corresponds to the first coloring of the Heawood graph up above.

For a decent puzzle, the Heawood graph is a little bit too small. Now, Hamiltonian cycles on trivalent graphs have been extensively studied (partially because of Tait’s conjecture, which turned out to be incorrect), so I suspect this phenomenon is known. There is a list of small symmetric cubic graphs, the Foster census, and it is no hard to write code that searches for more examples. Below is thus today’s puzzle, on Foster26A, also a map on a larger hexagonal torus. Complete it to make it triply Hamiltonian.