Does there exist a graph $G$ such that every edge is contained in a unique Hamiltonian circuit, that is not a cycle graph?

Question

Suppose $G$ is an (undirected, simple) finite graph. If $G$ is a cycle graph, then each edge of $G$ belongs to a unique Hamiltonian circuit. Does there exist a non-cycle graph $G$ with this property?

Answer 1

No such graph exists.

Every edge can be part of a Hamiltonian cycle, and the graph isn't a cycle. From these, we can deduce that:

1. At least two Hamiltonian cycles exist.
2. All vertices have valence > 2.
3. All vertices have valence > 3.
4. All vertices have even valence.
5. The connectivity > 3.

For 2, we merely need to use the two Hamiltonian cycles. They would necessarily need to overlap on the edges leading to the vertex of valence 2.

For 3, consider a vertex of valence 3, connected to vertices A, B, and C. If the edges leading to A or B are removed, then a cycle still exists. But that puts two different cycles going through the edge to C.

As a sidenote, that's what happens with the Markström graph. If any edge is deleted, the Hamiltonian cycle is then unique. But each edge supports two Hamiltonian cycles.

The Meredith Graph is an example of a 4-regular 4-connected graph with zero Hamiltonian cycles. After that, $K_5$ has 12 different Hamiltonian cycles, and that's the smallest possible number of Hamiltonian cycles for a 4-regular 4-connected Hamiltonian graph among graphs with <40 vertices.

Could the graph have valence 6? If so, removing 2 edges could make the graph non-Hamiltonian. Removing more edges would give a 5-connected 5-regular nonhamiltonian graph, which is impossible.

We're left with a 4-regular graph with more than 40 vertices. But it would also be a uniquely 4-colorable graph, and those are known to be the Apollonian networks -- and these graphs have more than 2 Hamiltonian cycles. So no such graph exists.

You'll need to settle for the Markström graph.