Minimum-order planar hypohamiltonian graph problem
A graph is hypohamiltonian if is non-Hamiltonian and, for every vertex , the graph is Hamiltonian. The conjecture is that the minimum order of a planar hypohamiltonian graph is , i.e., .
References
- Local modifications in planar hypohamiltonian graphs — arXiv — Samantha Durias, Sabrina Guerrero, Briana Jaiyen, Daniel Kaplan, Austin Lapine, Caleb Peralta, Akul Shrivastav
Source: arXiv
Progress summary
New constructions now cover every size from 36 upward, but the smallest possible size is unsettled: size 34 is conjectured minimal and size 35 remains open.
The problem asks for the minimum order of a planar hypohamiltonian graph. Chvátal posed the existence question in 1973; the current minimum-order question remains unresolved.
Known results
- Thomassen constructed an infinite family of planar hypohamiltonian graphs.
- Goedgebeur and Zamfirescu (2017) established the best cited lower bound, order at least .
- Tsai (2024) constructed examples of order , reducing the smallest known order from , but did not prove minimality.
- Tsai (2024) proved existence for every order at that time.
October 2026 constructions
Durias, Guerrero, Jaiyen, Kaplan, Lapine, Peralta, and Shrivastav report local modifications producing planar hypohamiltonian graphs at every order , together with additional small examples. This advances the existence classification but leaves order unresolved and does not prove that order is minimal.
Current status (as of October 2026): Existence is reported for every order , and order examples are known; whether order exists and whether any order below is possible remain open.
Solutions 0
No solutions have been posted yet.