Enumeration
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, “sufficiently large” is now known to mean that such graphs exist for all n ≥ 18. A complete list of hypohamiltonian graphs with at most 17 vertices is known: they are the 10-vertex Petersen graph, a 13-vertex graph and a 15-vertex graph found by computer searches of Herz (1968), and four 16-vertex graphs. There exist at least thirteen 18-vertex hypohamiltonian graphs. By applying the flip-flop method of Chvátal (1973) to the Petersen graph and the flower snark, it is possible to show that the number of hypohamiltonian graphs, and more specifically the number of hypohamiltonian snarks, grows as an exponential function of the number of vertices.
Read more about this topic: Hypohamiltonian Graph