Wiener–Araya graph
The Wiener–Araya graph is, in graph theory, a graph on 42 vertices with 67 edges. It is hypohamiltonian, which means that
it does not itself have a Hamiltonian cycle but every graph formed by removing a single vertex from it is Hamiltonian. It is also planar.

History

Hypohamiltonian graphs were first studied by Sousselier in Problèmes plaisants et délectables (1963).
In 1967, Lindgren built an infinite sequence of hypohamiltonian graphs.
He first cited Gaudin, Herz and Rossi, then Busacker and Saaty
as pioneers on this topic.

From the start, the smallest hypohamiltonian graph is known: the Petersen graph. However, the hunt for the smallest planar hypohamiltonian graph continues. This question was first raised by Václav Chvátal in 1973.
The first candidate answer was provided in 1976 by Carsten Thomassen, who exhibited a 105-vertices construction, the 105-Thomassen graph.
In 1979, Hatzel improved this result with a planar hypohamiltonian graph on 57 vertices : the Hatzel graph.
This bound  was lowered in 2007 by the 48-Zamfirescu graph.

In 2009, a graph built by Gábor Wiener and Makoto Araya became (with its 42 vertices) the smallest planar hypohamiltonian graph known.
In their paper, Wiener and Araya conjectured their graph to be optimal arguing that its order (42) appears to be the
answer to The Ultimate Question of Life, the Universe, and Everything from The Hitchhiker's Guide to the Galaxy, a Douglas Adams novel. However, subsequently, smaller planar hypohamiltonian graphs have been discovered.

References

External links
 

Individual graphs
Planar graphs