### 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:

- A graph is
*hypohamiltonian*if it does not contain a hamilton cycle, but the deletion of any vertex does create a hamilton cycle. - A
*planar*graph is a graph that can be embedded in the plane with no edge crossings. - A
*cubic*graph is a 3-regular graph. - 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].

Advertisements