Hypohamiltonian graphs of minimum degree at least 4

Status open high confidence

The question of whether there exists a hypohamiltonian graph with minimum degree at least 4 remains a longstanding open problem first posed by Thomassen (1978). The main structural constraint known is that every planar hypohamiltonian graph must contain a vertex of degree 3 (Thomassen), so any hypothetical example with minimum degree ≥ 4 must be non-planar. C. T. Zamfirescu later strengthened this by showing every planar hypohamiltonian graph contains at least four cubic vertices. Multiple papers from 2019–2025 continue to describe the general question as open.

Reviewer notes. Thomassen (1978) proved every planar hypohamiltonian graph contains a cubic vertex, ruling out planar examples with minimum degree ≥ 4. C. T. Zamfirescu strengthened this post-2008: every planar hypohamiltonian graph has at least four cubic vertices ('Cubic vertices in planar hypohamiltonian graphs', referenced in search results). All recent literature found (papers from 2019–2025 on hypohamiltonian graphs, including arXiv:1602.07171, arXiv:2311.10593, arXiv:2403.18384) consistently treat the existence of a hypohamiltonian graph with minimum degree ≥ 4 as open. No verified primary source reporting a resolution was found. Note: the cited Zamfirescu paper URL (czamfirescu.tricube.de/CTZamfirescu-32.pdf) returned a connection error and could not be verified, so it is not included in since_posted.

Auto-reviewed 2026-09-10 with claude-sonnet-4-6 (web search enabled).