← All problems

Minimum-order planar hypohamiltonian graph problem

A graph GG is hypohamiltonian if GG is non-Hamiltonian and, for every vertex v∈V(G)v\in V(G), the graph G−vG-v is Hamiltonian. The conjecture is that the minimum order of a planar hypohamiltonian graph is 3434, i.e., min⁡{∣V(G)∣:G is planar and hypohamiltonian}=34\min\{\lvert V(G)\rvert : G\text{ is planar and hypohamiltonian}\}=34.

References

Source: arXiv

Progress summary

Refreshed
Open · progress reported

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 2323.
  • Tsai (2024) constructed examples of order 3434, reducing the smallest known order from 4040, but did not prove minimality.
  • Tsai (2024) proved existence for every order n≥40n \ge 40 at that time.

October 2026 constructions

Durias, Guerrero, Jaiyen, Kaplan, Lapine, Peralta, and Shrivastav report local modifications producing planar hypohamiltonian graphs at every order n≥36n \ge 36, together with additional small examples. This advances the existence classification but leaves order 3535 unresolved and does not prove that order 3434 is minimal.

Current status (as of October 2026): Existence is reported for every order n≥36n \ge 36, and order 3434 examples are known; whether order 3535 exists and whether any order below 3434 is possible remain open.

Sources

Solutions 0

No solutions have been posted yet.