3-connected planar bipartite graph without a Hamiltonian path

bipartite-graphsgraph theoryhamiltonian-pathplanar-graphs

I'm stuck with exercise 18.1.5 of Bondy & Murty's Graph Theory book which asks for an example of a 3-connected planar bipartite graph on fourteen vertices that is not traceable (that is, which has no Hamiltonian path).

I'm aware of Barnette's conjecture which states that every cubic 3-connected planar bipartite graph is Hamiltonian and I know that such a small counterexample on fourteen vertices does not exist, so if I'm right the 3-connected bipartite planar graph that I'm looking for has minimum degree at least three and it must have at least a vertex of degree greater than 3 but all the graphs that I have drawn fail to fulfill one of the conditions (planarity, 3-connectedness or being bipartite).

Even if such an example was found, I would still need to prove that it has no Hamiltonian path which doesn't seem easy either. For the examples that I was trying to build, I was considering all the possible paths going through a vertex to show that it is not traceable, but that's a very long task.

Any hints or ideas would be much appreciated.

Best Answer

Checking if a given graph has a Hamiltonian path is hard; however, cooking up examples of graphs that definitely don't have Hamiltonian paths is much easier. For example, if the graph didn't have to be planar, then you could take the complete bipartite graph $K_{6,8}$. This does not have a Hamiltonian path because any path alternates sides of the graph, but this bipartite graph is unbalanced so you would run out of vertices on the side with $6$ vertices before visiting all of the vertices on the other side.

There is a planar example that fails to have a Hamiltonian path for a similar reason: the skeleton graph of the rhombic dodecahedron. This polyhedron is constructed by putting square pyramids on the faces of a cube in such a way that the sides of adjacent pyramids line up and we end up with six diamond-shaped faces.

The graph is a subgraph of $K_{6,8}$: the vertices that were vertices of the cube are only adjacent to the vertices that form the tips of the pyramids, and vice versa. So it's bipartite and not Hamiltonian. It's planar and $3$-connected because it's the skeleton graph of a polyhedron: the polyhedral graphs are precisely the $3$-connected planar graphs.

Finally, here is one way to solve this problem that probably goes against the spirit of the exercise but is very much in the spirit of doing independent work in graph theory. Go to the House of Graphs and run the following search:

Require a specific (numeric) value for an invariant: "Number of vertices equal to 14" and "Vertex Connectivity greater than or equal to 3"
Only consider certain classes of graphs: "Planar", "Bipartite", and NOT "Traceable".

This will give you exactly one result, which is the rhombic dodecahedral graph.

Related Solutions

[Math] Connected bipartite graph

Let the two parts of the graph be $A$ and $B$ if it is not connected then it contains $k\geq2$ connected components. Each of these connected components contains at least $\frac{n}{4}+1$ vertices in $A$ and at least $\frac{n}{4}+1$ vertices in $B$. So each connected component has at least $\frac{n}{2}+2$ vertices. So if we have $k$ connected components we need $\frac{kn}{2}+2k$ vertices, even for $k=2$ we get $n+4$ vertices. So it is impossible for $G$ to be disconnected.

[Math] Can a bipartite graph have many Hamiltonian paths but no Hamiltonian cycle

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.

Best Answer

Related Solutions

[Math] Connected bipartite graph

[Math] Can a bipartite graph have many Hamiltonian paths but no Hamiltonian cycle

Related Question