Hypohamiltonian Planar Graphs

Brendan McKay uploaded a short-but-sweet article to the arXiv titled Hypohamiltonian planar cubic graphs with girth five. Let’s quickly break down all of the words of this title:

1. A graph is hypohamiltonian if it does not contain a hamilton cycle, but the deletion of any vertex does create a hamilton cycle.
2. A planar graph is a graph that can be embedded in the plane with no edge crossings.
3. A cubic graph is a 3-regular graph.
4. The girth of a graph is the length of the shortest cycle.

McKay details the search for the smallest (and first known) graphs of this type, which have order 76. There are three non-isomorphic examples. The data for these graphs (and more) is available online [Note: at this time, it appears the data is not yet online].

The three smallest examples of hypohamiltonian planar cubic graphs of girth 5. The numbers give the face lengths for faces other than 5-faces. Figures by B.D. McKay.