On Cubic Planar Hypohamiltonian and Hypotraceable Graphs

Abstract

We present a cubic planar hypohamiltonian graph on 70 vertices, improving the best known bound of 94 by Thomassen and derive some consequences concerning longest paths and cycles of planar $3$-connected graphs. We also show that cubic planar hypohamiltonian graphs on $n$ vertices exist for every even number $n\geq 86$ and that cubic planar hypotraceable graphs exist on $n$ vertices for every even number $n \geq 356$, settling an open question of Holton and Sheehan.