A graph G is hypohamiltonian if G is nonhamiltonian, but G - v is Hamiltonian for every v element V. The Petersen graph, which has ten nodes, is the smallest hypohamiltonian graph and the only such graph on ten nodes. Herz et al. (1967) showed that there are no hypohamiltonian graphs with 11 or 12 vertices. By parity, no bipartite graph is hypohamiltonian. Many (but not all) snarks are hypohamiltonian. Hypohamiltonian graphs are almost Hamiltonian. Sousselier (in Herz et al. 1967) and Lindgren independently constructed the same sequence of hypohamiltonian graphs with 6k + 10 vertices, illustrated above (which includes the Petersen graph on 10 vertices).

almost Hamiltonian graph | Araya-Wiener graphs | Hamiltonian graph | Hatzel graph | hypotraceable graph | Petersen graph | planar hypohamiltonian graph | snark | traceable graph | Wiener-Araya graph | Zamfirescu graphs