Can a bipartite graph have many Hamiltonian paths but no Hamiltonian cycle?

Solution 1:

Yes! The Georges graph has this property. This graph is the smallest known counterexample to the Tutte conjecture that any 3-connected bipartite 3-regular graph is Hamiltonian. It has 50 vertices and 75 edges.

I verified that every vertex is the initial vertex of a Hamiltonian path with some Sage code:

def homtrac_orbits(g):
    orbits = g.automorphism_group(return_group=False, orbits=True)
    return all(g.hamiltonian_path(o[0]) is not None for o in orbits)

def report(G):
    print G.name() + ':', homtrac_orbits(G), G.is_hamiltonian(), G.is_bipartite()

report(Graph(">>graph6<<qO`a`_WO?O?_?_?OO???K?@O?B_?@??__?_I?A?_?_????@?A?@???\
O????g???`????C????????A?????O????C??????????K?????K?????S?????K?????\
B????OO?????__??????C??????C??????A?????C????????D_??????I???????[\
??????AG??????GA_", name="Georges"))

You can see it on SageCell but it takes some time to run. It prints "Georges: True False True" when complete.

The Ellingham-Horton graphs on 54 and 78 vertices are also homogeneously traceable but non-Hamiltonian. The 54-graph can be checked with

report(graphs.EllinghamHorton54Graph())

(included in the above SageCell). I also checked the 78-graph but this is too slow to include in the SageCell.

It seems reasonable to guess that the other known counterexamples to Tutte's conjecture—namely the Owens graph, the Horton 92-graph, and the Horton graph—are also homogeneously traceable, but checking in Sage is too slow for those to verify that way.