# 2- or 3-vertex-connected cubic planar bipartite graphs with only one Hamilton cycles

Hamiltonicity remains NP-complete for 2-vertex-connected cubic planar bipartite graphs.
What is the smallest 2- or 3-vertex-connected cubic planar bipartite graph with only one (forward and backward counted as one) Hamilton cycle (HC)?

I thought asymmetry might help, but even Frucht’s graph, a non-bipartite example, seems to have more than one HC…

$\phantom{}$

And if a single HC is not possible, what is the smallest number and how does the corresponding graph look like?

#### Solutions Collecting From Web of "2- or 3-vertex-connected cubic planar bipartite graphs with only one Hamilton cycles"

This paper here seems to suggest that this is impossible. Theorem 1 states that every cubic Hamiltonian graph has at least three Hamiltonian cycles and theorem 10 states that if the graphs are additionally bipartite then they have at least four Hamiltonian cycles.

The article contains quite a few other results which pertain to the subject and it might be of interest to you to peruse through.

Based on EuYu, it appears there is no such graph. I originally deleted my answer after that. But, now I put it back so the code is visible. This code will find examples of graphs that satisfy all the conditions EXCEPT the unique Hamilton cycle.

Using Sage, including the nauty generator of graphs, we can generate all graphs with 3 * ord / 2 edges easily. Of course, we only need check graphs with even order as well. So, this should go quick for graphs of small order. But, even at order 12 it might take a very long time. There are over 10 billion graphs of order 12, not sure how many have 18 edges exactly.

# ord must be even
ord = 12
num_edges = 3 * (ord/2)
# This is the string that gets put in the nauty generator to tell it which
# graphs to generate
# E.g., "12 18:18 -c" says generate order 12 graphs with 18 edges that are connected.
nauty_string = str(ord) + " " + str(num_edges) + ":" + str(num_edges) + " -c"
for g in graphs.nauty_geng(nauty_string):

# check min degree is 3.  Since we have the constraint on edges above
# this should guarantee the max degree is 3 as well.
deg = g.degree()
deg.sort()
if deg[0] == 3:
if g.is_bipartite():
if g.is_planar():
vert_conn = g.vertex_connectivity()
if vert_conn >=2:
if vert_conn <=3:
if g.is_hamiltonian():
print g.graph6_string()
print "Finished with", ord