Hypohamiltonian graph

[2] Concepts closely related to hypohamiltonicity have also been used by Park, Lim & Kim (2007) to measure the fault tolerance of network topologies for parallel computing.

Every hypohamiltonian graph must be 3-vertex-connected, as the removal of any two vertices leaves a Hamiltonian path, which is connected.

There exist n-vertex hypohamiltonian graphs in which the maximum degree is n/2, and in which there are approximately n2/4 edges.

For some time it was unknown whether a hypohamiltonian graph could be planar, but several examples are now known,[4] the smallest of which has 40 vertices.

[7] A 3-coloring of this subgraph can be simply described: after removing one vertex, the remaining vertices contain a Hamiltonian cycle.

Lindgren (1967) found another infinite class of hypohamiltonian graphs in which the number of vertices is 4 mod 6.

Václav Chvátal proved in 1973 that for all sufficiently large n there exists a hypohamiltonian graph with n vertices.

Taking into account subsequent discoveries,[10] “sufficiently large” is now known to mean that such graphs exist for all n ≥ 18.