Hamiltonian Path on Cubic Graphs, and whether closed triangle meshes are triangle strips

Question

The problem is this:

Can every closed triangle mesh (an approximation of a 3d object using triangles, eg. a tetrahedron) be 'peeled like an orange', that is, can we find a sequence of triangles such that consecutive triangles share edges, and all triangles in the mesh are included once (and only once) in our sequence.

This is my logic so far:

Model the mesh as its dual graph, where vertices are triangles, and edges join triangles that share edges, then the problem boils down to finding a Hamiltonian Path in the graph.

Each vertex will have degree three; this makes the graph by definition cubic.

I did some googling; I did find that Tait's conjecture, that every cubic polyhedral graph has a Hamiltonian cycle, is false. I guess then that every cubic polyhedral graph has a Hamiltonian path (otherwise a counterexample would disprove Tait's conjecture). Cubic polyhedral graphs are planar and 3-vertex-connected so if my guess is correct, we can 'peel' all convex polyhedra, but can we always 'peel' a torus?

I believe that if our 3d mesh is an object without holes, then the graph is always planar.

So my question is:

When are Hamiltonian paths guaranteed to exist in cubic graphs? Particularly those cubic graphs that correspond to physical triangle meshes.

In my quest for a counterexample I constructed a genus-2 surface out of triangles, but it was fairly easy for my computer to find a 'peeling', so I am now a little more convinced that everything can be peeled.

Answer 1

I found a paper that gives the required example.

The first graph in this paper shows an 88 vertex planar cubic graph that doesn't have any Hamiltonian path:

The dual of this would be a 3d convex polyhedron made of 88 triangles (Garuanteed by Steinitz Theorem, as noted by Henning Makholm) that cannot be 'peeled'. It can be realised as a tetrahedron, with the base a single triangle, and the sides an arrangement of 29 triangles:

The example makes use of what it calls a 'Tutte Triangle': $abc$ - a graph with the property that any path joining $b$ and $c$ cannot pass through all vertices of $abc$.

Answer 2

The dual of the Tutte graph would be a counterexample to the existence of a Hamiltonian cycle. But the Tutte graph does have a Hamiltonian path.

On the other hand, we can use the Tutte fragment to construct a polyhedral 3-regular graph that doesn't even have a Hamiltonian path: Take the graph of a cube, allow two vertices opposite each other to remain vertices, and replace each of the other six vertices with a Tutte fragment "pointing towards" the selected cube vertex, producing this:

which (by Steinitz's theorem) you can draw on a sphere and dualize to get this unpeelable triangle mesh (imagine folding the figure into an octahedron):

---

I doubt you can find an easy necessary and sufficient criterion, since the NP-hardness of finding Hamiltonian cycles seems to be quite robust.

If your triangle mesh can be 2-colored (that is, the underlying cubic graph is bipartite), a Hamiltonian cycle may be guaranteed; this is the unsolved Barnette's conjecture.

[1]: