# What is the smallest uniquely hamiltonian graph with minimum degree at least 3?

I would like to know more about uniquely hamiltonian graphs with minimum vertex degree at least 3, and in particular what is the smallest one.

(Recall that a graph is hamiltonian if it has a cycle passing through each vertex exactly once, and is uniquely hamiltonian if there is only one such cycle.)

Here's the smallest one that I currently know.

Does anyone know if a smaller one (fewer vertices) has been published?

• What are the numbers placed for? They definitely don't indicate the cycle (which is obvious). Do they bear some additional info? – Ilya Bogdanov Nov 28 '16 at 9:18
• The numbers are just an arbitrary labelling so no further information there. – Gordon Royle Nov 28 '16 at 9:24
• A google search brings up this article: link.springer.com/chapter/10.1007%2F978-3-319-39636-1_1. And it claims there is such a graph on only 10 vertices. – Wolfgang Nov 28 '16 at 11:10
• @Wolfgang This is a very strange paper. I agree that it claims that there is such a graph on 10 vertices. However it does not actually contain any graphs, except for a diagram (Figure 1) of a 10-vertex graph that is not uniquely hamiltonian. The paper spends almost all its time on an extended description of a search algorithm that judging by the number of acronyms used must be quite complicated, and plenty of tables of running times and success rates etc. But no uniquely hamiltonian graphs :-( – Gordon Royle Nov 28 '16 at 12:05
• Aha, figured it out. The 10-vertex graph in the aforementioned paper has the property that it has an edge that is contained in only one hamilton cycle. This means it can be turned into a uniquely hamiltonian graph via a simple doubling procedure. So while the 10-vertex graph itself is not uniquely hamiltonian, it leads to a 20-vertex example that is. – Gordon Royle Nov 28 '16 at 12:34

I am not sure what the smallest such graph is, but since you also asked for more information on uniquely hamiltonian graphs with minimum degree $3$, Entringer and Swart proved the following nice theorem.
For each $n= 2k, k \geqslant 11$, there exists a uniquely hamiltonian graph on $n$ vertices having two vertices of degree $4$ and all others of degree $3$.