Goldner–Harary graph

Goldner–Harary graph
Named after	A. Goldner, Frank Harary
Vertices	11
Edges	27
Radius	2
Diameter	2
Girth	3
Automorphisms	12 (D6)
Chromatic number	4
Chromatic index	8
Properties	Polyhedral Planar Chordal Perfect Treewidth 3

In the mathematical field of graph theory, the Goldner–Harary graph is a simple undirected graph with 11 vertices and 27 edges. It is named after A. Goldner and Frank Harary, who proved in 1975 that it was the smallest non-Hamiltonian maximal planar graph. The same graph had already been given as an example of a non-Hamiltonian simplicial polyhedron by Branko Grünbaum in 1967.

The Goldner–Harary graph is a planar graph: it can be drawn in the plane with none of its edges crossing. When drawn on a plane, all its faces are triangular, making it a maximal planar graph. As with every maximal planar graph, it is also 3-vertex-connected: the removal of any two of its vertices leaves a connected subgraph.

The Goldner–Harary graph is also non-hamiltonian. The smallest possible number of vertices for a non-hamiltonian polyhedral graph is 11. Therefore, the Goldner–Harary graph is a minimal example of graphs of this type. However, the Herschel graph, another non-Hamiltonian polyhedron with 11 vertices, has fewer edges.

As a non-Hamiltonian maximal planar graph, the Goldner–Harary graph provides an example of a planar graph with book thickness greater than two. Based on the existence of such examples, Bernhart and Kainen conjectured that the book thickness of planar graphs could be made arbitrarily large, but it was subsequently shown that all planar graphs have book thickness at most four.

It has book thickness 3, chromatic number 4, chromatic index 8, girth 3, radius 2, diameter 2 and is a 3-edge-connected graph.

...
Wikipedia