Can a bipartite graph with at least three vertices have the following properties simultaneously:
- Every vertex is the initial vertex of some Hamiltonian path.
- The graph contains no Hamiltonian cycle.
I found out that this is only possible if the number of vertices is even and if the partitions have equal size. My conjecture is that there is no bipartite graph with the desired properties, but I cannot prove it.
Best Answer
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:
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
(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.