How does the Hamilton Cycle of $\bf \{6,3\}_{(1,3)}$ look like?

Question

I got a knot in my brain while trying to find whether this graph

is hamiltonian. It has 14 vertices, 7 faces and 21 edges and is embedded on a genus 1 surface (torus). Can anyone help?

7 faces in the plane would be a killer argument in the plane due to Grinbergs Theorem, but things are slightly more complicated on surfaces with a higher genus...

UPDATE since the graph is (related to) Heawood's graph, it is hamiltonian. But how the Hamilton Cyclew look?

...and if anyone knows whether all hexagonal graphs listed there are hamiltonian, I would also be glad to know...

Answer 1

The "just go straight" strategy seems to work pretty well on a fair number of examples.

And when the "just go straight" strategy doesn't work out (because some needed arithmetic condition is not satisfied), the "just go straight with a twist" strategy should win everytime. First, just go straight ; this gives you finitely many cycles.

All these cycles are isomorphic. Then jump from one cycle to the next to link them all.

So I am going to guess that all these graphs are Hamiltonian.

Answer 2

In this solution I am going to assume that the edges crossing the purple boundary of the hexagon are never used. It turns out that by removing such edges the count of hamiltonian paths is greatly simplified.

Such graph has $6$ nodes with degree $2$: they can be removed and their neighbours can be joined by an arc (any hamiltonian cycle has a forced path through any vertex with degree $2$). With this reduction we get a graph on $8$ vertices: $6$ vertices form a $C_6$, the "even" vertices of such cycle are connected with $A$, the "odd" vertices are connected with $B$ and $A,B$ are connected to each other, leading to $13$ edges forming the skeleton of a cube, plus a diagonal:

If we just ignore the diagonal, we already have twelve hamiltonian paths for the skeleton of a cube.
The vertices of a cube can be colored in such a way that the neighbourhood of any "blue" vertex is "yellow" and vice-versa. The endpoints of a diagonal are opposite-colored, so we are looking for hamiltonian cycles in a bipartite graph with the following structure:

We have four vertices on each side, $A_1,B_1,C_1,D_1$ and $A_2,B_2,C_2,D_2$. $X_i$ and $Y_j$ are connected if $X\neq Y$ and $i\neq j$, but we have an extra edge joining $A_1$ and $A_2$ (the previous diagonal). The total number of hamiltonian cycles is given by $12$ (the hamiltonian cycles on the skeleton of a cube) plus $6$ (the ones through $A_1 A_2$).