On cubic planar hypohamiltonian and hypotraceable graphs (Q540080)

Summary: 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.