ArticleslgStudy

science

Goldner–Harary graph

Goldner–Harary graph is a science topic covered in the lgStudy science library. This page brings together a partial reference excerpt, illustrations, worked examples, real-world applications and a short study plan, so you can understand Goldner–Harary graph rather than just read about it. In short: 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 Anita M.

Goldner–Harary graph — main illustration
Goldner–Harary graph — illustration

Key takeaways

  • Goldner–Harary graph belongs to science; place it in that map before memorising details.
  • Learn the definition first, then one example that makes the definition concrete.
  • Connect Goldner–Harary graph to a quantity you can measure, compute or draw — that is where exam questions come from.
  • Reproduce the core statement of Goldner–Harary graph from memory before moving on to harder problems.

Reference excerpt

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 Anita M. 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.

Properties 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 non-Hamiltonian, meaning there cannot exist a cycle passing once through each of the eleven vertices. The smallest possible number of vertices for a non-Hamiltonian polyhedral graph is 11. Therefore, the Goldner–Harary graph is a minimal example of this type. However, the Herschel graph, another non-Hamiltonian polyhedron with 11 vertices, has fewer edges. The Goldner–Harary is 3-tree, constructed from a complete graph on two vertices, repeatedly adding vertices until the graph has exactly three neighbors, which forms a clique. Like any k {\displaystyle k} -tree, it has treewidth 3, and its graph is maximal, meaning it can add no more edges without increasing its treewidth. Both of its maximal cliques and clique separators have the same size, hence the graph is chordal. As a planar 3-tree, it forms an example of an Apollonian network.

As a non-Hamiltonian maximal planar graph, the Goldner–Harary graph provides an example of a planar graph with book thickness greater than two. Equivalently, it does not have a planar arc diagram with all vertices on a line and all edges drawn as curves that stay on a single side of the line. Based on the existence of such examples, Bernhart and Kainen conjectured that the book thickness of planar graphs could be made arbitrarily large. Nonetheless, 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. The automorphism group of the Goldner–Harary graph is of order 12 and is isomorphic to the dihedral group D6, the group of symmetries of a regular hexagon, including both rotations and reflections. The characteristic polynomial of the Goldner–Harary graph is : − ( x − 1 ) 2 x 2 ( x + 2 ) 3 ( x 2 − 3 ) ( x 2 − 4 x − 9 ) {\displaystyle -(x-1)^{2}x^{2}(x+2)^{3}(x^{2}-3)(x^{2}-4x-9)} .

Polyhedron

By Steinitz's theorem, the Goldner–Harary graph is a polyhedral graph: it is 3-connected planar, so there exists a convex polyhedron having the Goldner–Harary graph as its skeleton. Geometrically, the Goldner–Harary graph represents a simplicial polyhedron, a polyhedron with triangular faces. The polyhedron is constructed by gluing tetrahedra onto each face of a triangular dipyramid, the Kleetope of the triangular dipyramid. If the tetrahedra are regular tetrahedron, meaning their faces are equilateral triangles and all edges are of equal length, the result is a non-convex deltahedron. The dual graph of the Goldner–Harary graph is represented geometrically by the truncation of the triangular prism.

References

Mincu, R.; Obreja, C.; Popa, A. (4–7 September 2019), "The Graceful Chromatic Number for Some Particular Classes of Graphs", 2019 21st International Symposium on Symbolic and Numeric Algorithms for Scientific Computing (SYNASC), pp. 109–115, doi:10.1109/SYNASC49474.2019.00024, ISBN 978-1-7281-5724-5. Sercek, Ilknur; Sampathila, Niranjana; Tasci, Irem; Ekmekyapar, Tuba; Tasci, Burak; Barua, Prabal Datta; Baygin, Mehmet Baygin; Dogan, Sengul; Tuncer, Turker; Tan, Ru-San; Acharya, U. R. (2025), "A new quantum-inspired pattern based on Goldner–Harary graph for automated Alzheimer's disease detection", Cognitive Neurodynamics, 19 (71) 71: 1–19, doi:10.1007/s11571-025-10249-7, PMC 12065701 Zamfirescu, Carol T. (2022), "On the hamiltonicity of a planar graph and its vertex-deleted subgraphs", Journal of Graph Theory, 102 (1): 180–193, doi:10.1002/jgt.22864, hdl:1854/LU-01GQ0AM8QAQFDDQ14D9HKADFT3.

External links Weisstein, Eric W., "Goldner-Harary graph", MathWorld

Illustrations

Goldner–Harary graph illustration
Goldner–Harary graph: An arc diagram of the Goldner–Harary graph. This graph has no Hamiltonian cycle, but can be made Hamiltonian by subdividing the edge crossed by the red dashed line segment and adding two edges along this segment.
An arc diagram of the Goldner–Harary graph. This graph has no Hamiltonian cycle, but can be made Hamiltonian by subdividing the edge crossed by the red dashed line segment and adding two edges along this segment.
Goldner–Harary graph: Realization of the Goldner–Harary graph as a convex polyhedron.
Realization of the Goldner–Harary graph as a convex polyhedron.

Worked examples

Example 1 — a first encounter with Goldner–Harary graph

Start with the simplest possible case. Write down what Goldner–Harary graph claims or describes in one sentence, then invent the smallest concrete situation in which that sentence is true. In science, the smallest case is usually a single object, a single equation or a single measurement. Check that every symbol or term in your sentence has a meaning in that case.

Example 2 — changing one variable

Take the situation from Example 1 and change exactly one quantity: double it, halve it, or set it to zero. Predict what should happen to Goldner–Harary graph before you calculate. Comparing your prediction with the result is the fastest way to find out whether you understand the idea or only the words.

Example 3 — an exam-style question

Typical questions about Goldner–Harary graph ask you to (a) state it precisely, (b) apply it to given data, and (c) explain a limitation. Practise writing all three answers in under five minutes; the third part is what separates a full-mark answer from an average one.

Applications of Goldner–Harary graph

In research
Goldner–Harary graph appears in science research whenever the underlying quantities have to be modelled precisely. Papers usually cite it as a starting assumption and then explore where it breaks down.
In technology and industry
Engineering practice reuses Goldner–Harary graph in design rules, simulations and safety margins. Knowing the idea lets you read a specification sheet and understand why the numbers look the way they do.
In the classroom
Goldner–Harary graph is common in secondary-school and first-year university syllabi. It links to neighbouring topics Individual graphs, Planar graphs, so understanding it makes those chapters shorter.
In everyday life
Look for Goldner–Harary graph outside the textbook — in sport, cooking, traffic, electronics or the sky above you. An example you found yourself is remembered far longer than one you were given.
Ask Teacher Smith questions about this articleOpens your AI tutor with a question about “Goldner–Harary graph” →

Affiliate

Preply — study more efficiently by working with a personal tutor. 50% off.

How to study Goldner–Harary graph in 20 minutes

  1. Read the reference excerpt below once, without taking notes.
  2. Close the page and write down what Goldner–Harary graph means in your own words.
  3. Compare your version with the excerpt and mark what you missed.
  4. Work through the three examples above with pen and paper.
  5. Explain Goldner–Harary graph out loud to somebody else — or to Teacher Smith in the lgStudy chat.

Frequently asked questions

What is Goldner–Harary graph in simple terms?

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 Anita M.

Why does Goldner–Harary graph matter?

Because it connects several science ideas at once: it gives you a definition you can apply, a quantity you can calculate, and a way to check whether a result is plausible.

How should I study Goldner–Harary graph?

Read the excerpt, restate it from memory, then work through the examples and applications listed on this page. The five-step study plan above takes about twenty minutes.

What does this page cover?

It gives you a compact reference excerpt plus original lgStudy explanations, examples, applications and study material on Goldner–Harary graph.

Tags

  • Individual graphs
  • Planar graphs

Keep exploring