The Wiener–Araya graph is, in

graph theory In mathematics and computer science, graph theory is the study of ''graph (discrete mathematics), graphs'', which are mathematical structures used to model pairwise relations between objects. A graph in this context is made up of ''Vertex (graph ...

, a graph on 42 vertices with 67 edges. It is hypohamiltonian, which means that it does not itself have a

Hamiltonian cycle In the mathematics, mathematical field of graph theory, a Hamiltonian path (or traceable path) is a path (graph theory), path in an undirected or directed graph that visits each vertex (graph theory), vertex exactly once. A Hamiltonian cycle (or ...

but every graph formed by removing a single vertex from it is

Hamiltonian Hamiltonian may refer to: * Hamiltonian mechanics, a function that represents the total energy of a system * Hamiltonian (quantum mechanics), an operator corresponding to the total energy of that system ** Dyall Hamiltonian, a modified Hamiltonian ...

. It is also

planar Planar is an adjective meaning "relating to a plane (geometry)". Planar may also refer to: Science and technology * Planar (computer graphics), computer graphics pixel information from several bitplanes * Planar (transmission line technologies), ...

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 In the mathematics, mathematical field of graph theory, a graph (discrete mathematics), graph ''G'' is said to be hypohamiltonian if ''G'' itself does not have a Hamiltonian cycle but every graph formed by removing a single vertex from ''G'' is H ...

is known: the

Petersen graph In the mathematical field of graph theory, the Petersen graph is an undirected graph with 10 vertices and 15 edges. It is a small graph that serves as a useful example and counterexample for many problems in graph theory. The Petersen graph i ...

. However, the hunt for the smallest

continues. This question was first raised by

Václav Chvátal Václav (Vašek) Chvátal () is a Professor Emeritus in the Department of Computer Science and Software Engineering at Concordia University in Montreal, Quebec, Canada, and a visiting professor at Charles University in Prague. He has published ex ...

in 1973. The first candidate answer was provided in 1976 by

Carsten Thomassen Carsten Thomassen may refer to: * Carsten Thomassen (mathematician) Carsten Thomassen (born August 22, 1948 in Grindsted) is a Danish mathematician. He has been a Professor of Mathematics at the Technical University of Denmark since 1981, and ...

, who exhibited a 105-vertices construction, the

105-Thomassen graph 1 (one, unit, unity) is a number, numeral, and glyph. It is the first and smallest positive integer of the infinite sequence of natural numbers. This fundamental property has led to its unique uses in other fields, ranging from science to sp ...

. In 1979, Hatzel improved this result with a

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

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 ''The Hitchhiker's Guide to the Galaxy'' is a comic science fiction series created by Douglas Adams that has become popular among fans of the genre and members of the scientific community. Phrases from it are widely recognised and often used in ...

from

The Hitchhiker's Guide to the Galaxy ''The Hitchhiker's Guide to the Galaxy'' is a Science fiction comedy, comedy science fiction franchise created by Douglas Adams. Originally a The Hitchhiker's Guide to the Galaxy (radio series), radio sitcom broadcast over two series on BBC ...

, a

Douglas Adams Douglas Noel Adams (11 March 1952 – 11 May 2001) was an English author, humorist, and screenwriter, best known as the creator of ''The Hitchhiker's Guide to the Galaxy''. Originally a 1978 BBC radio comedy, ''The Hitchhiker's Guide to the ...

novel. However, subsequently, smaller planar hypohamiltonian graphs have been discovered.

References

External links

* {{DEFAULTSORT:Wiener-Araya graph Individual graphs Planar graphs