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.


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:

        Number of Vertices = 14.0
AND     Planar = true
AND     Bipartite = true
AND     Hamiltonian = false
AND     Vertex Connectivity >= 3.0

This will give you exactly one result, which is the rhombic dodecahedral graph. (Technically, the condition Hamiltonian = false only ensures the graph does not have a Hamiltonian cycle, so we should double-check that this graph doesn't have a Hamiltonian path, either.)

  • $\begingroup$ Thank you very much. I was unaware of the website from which you got the answer and it might certainly go against the spirit of the exercise, but definitely not against the spirit of doing independent research or work in graph theory or any other area of Mathematics. Yes, I knew that if one of the parts of the bipartition had greater size than the other one, then it would be impossible for the graph to have a Hamiltonian path and fortunately this is actually the case for the rhombic dodecahedral. Thank you very much for your answer and for letting me know about such a useful website. $\endgroup$ – user594756 Sep 20 '18 at 2:30
  • $\begingroup$ The size of the parts must differ by at least 2 to guarantee no Hamiltonian path.u $\endgroup$ – Gordon Royle Sep 20 '18 at 11:55
  • $\begingroup$ @GordonRoyle Fortunately, 6 and 8 do differ by at least 2. $\endgroup$ – Misha Lavrov Sep 20 '18 at 15:05
  • $\begingroup$ Indeed, I was just correcting the previous comment. $\endgroup$ – Gordon Royle Sep 20 '18 at 23:28

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.