2
$\begingroup$

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.

$\endgroup$

1 Answer 1

2
$\begingroup$

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.

$\endgroup$
4
  • $\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, 2018 at 2:30
  • 1
    $\begingroup$ The size of the parts must differ by at least 2 to guarantee no Hamiltonian path.u $\endgroup$ Sep 20, 2018 at 11:55
  • $\begingroup$ @GordonRoyle Fortunately, 6 and 8 do differ by at least 2. $\endgroup$ Sep 20, 2018 at 15:05
  • $\begingroup$ Indeed, I was just correcting the previous comment. $\endgroup$ Sep 20, 2018 at 23:28

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .