An almost hypohamiltonian graph is a nonhamiltonian graph whose vertex-deleted subgraphs are Hamiltonian with exactly one exception. Specifically,
a graph 
is almost hypohamiltonian if there exists a vertex 
such that 
is nonhamiltonian
but 
is Hamiltonian for all vertices 
. The vertex 
may be termed the "exceptional vertex" (Goedgebeur
and Zamfirescu 2019, Tsai 2025).
Wiener (2018) gave examples of planar almost hypohamiltonian graphs on 31 and 36 vertices. Durias et al. (2026) constructed planar
examples of every order 
. They devised the approach and examples themselves,
using AI-generated code to check Hamiltonian cycles.
Zamfirescu (2019) proved every planar almost hypohamiltonian
graph has a cubic vertex which is not the exceptional vertex (Tsai 2025).
Zamfirescu (2015) found a smallest almost hypohamiltonian graph, which has 17 vertices (Zamfirescu 2015, Goedgebeur and Zamfirescu 2019). Goedgebeur and Zamfirescu (2019) found a smallest almost hypohamiltonian graph of girth 4, which has 18 vertices.
No planar almost hypohamiltonian graph of girth 3 is known (Goedgebeur and Zamfirescu 2019, Tsai 2025).
The following table gives counts of small almost hypohamiltonian graphs in various classes (Goedgebeur and Zamfirescu 2019).
| class | girth | vertex count | number |
| almost hypohamiltonian | 5 | 17 | 2 |
| almost hypohamiltonian | 5 | 18 | 1 |
| almost hypohamiltonian | 4 | 18 | 1 |
| cubic almost hypohamiltonian | 5 | 26 | 10 |
| cubic almost hypohamiltonian | 5 | 28 | 2 |
| cubic almost hypohamiltonian | 4 | 28 | 4 |
| planar almost hypohamiltonian | 5 | 44 | 1 |
| planar cubic almost hypohamiltonian | 5 | 68 | 3 |
