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 Zamfirescu1 2019, Tsai 2024).
Wiener (2018) gave examples of planar almost hypohamiltonian graphs on 31 and 36 vertices. Zamfirescu (2019) proved every planar almost hypohamiltonian graph has a cubic vertex which is not the exceptional vertex (Tsai 2024).
Zamfirescu (2015) found a smallest almost hypohamiltonian graph, which has 17 vertices (Zamfirescu 2015, Goedgebeur and Zamfirescu 2019). Goedgebeur and Zamfirescu1 (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 2014).
The following table summarizes the smallest almost hypohamiltonian graphs satisfying various crietria (Goedgebeur and Zamfirescu 2019).
| class | girth | smallest 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 |
