Local modifications in planar hypohamiltonian graphs

Abstract

We prove that for $n\ge 36$ there exists a planar hypohamiltonian graph of order $n$. As a corollary, we prove that for $n\ge 33$ there exists an almost hypohamiltonian planar graph of order $n$. Further, we exhibit over 100 planar hypohamiltonian graphs of order less than 40, including new graphs of orders 36, 37, 38, and 39. The proof utilizes three local modifications that alter a graph $G$ by removing a subgraph $H$ and replacing it with $H^{\prime }$ to form a new graph $G^{\prime }$: a plus two modification, a plus three modification, and Thomassen's iterable plus four modification. The plus two modification preserves hypohamiltonicity in general, and the plus three modification preserves hypohamiltonicity in our cases of interest. This establishes the main result beginning with Tsai's order 34 examples. Further, we conjecture that among planar hypohamiltonian graphs, Tsai's 34 vertex examples are the smallest order. The conjecture is based on previous results, constraints on the degree modulo 3, and experimentation with planar graphs consisting entirely of 4-gons and 5-gons.

30 pages, comments welcome