TOPICS
Search

Polyhedral Nonhamiltonian Graph

DOWNLOAD Mathematica NotebookDownload Wolfram Notebook

A polyhedral nonhamiltonian graph is a graph that is simultaneously polyhedral and nonhamiltonian.

The smallest possible number of vertices a nonhamiltonian polyhedral graph can have is 11, and there exist 74 such graphs, as summarized in the table below.

edge countcountnames
181Herschel graph
192
206
2112
2216
2316
2412
256
262
271Goldner-Harary graph

The numbers of polyhedral nonhamiltonian graphs n=11, 12, ... vertices are 74, 1600, 43984, 1032208, 22960220, ... (OEIS A007033).

Tait's Hamiltonian graph conjecture asserted that every cubic polyhedral graph is Hamiltonian. It was proposed by Tait in 1880 and refuted by Tutte (1946) with a counterexample on 46 vertices (Tutte's graph).

See also

Cubic Nonhamiltonian Graph, Goldner-Harary Graph, Herschel Graph, Nonhamiltonian Graph, Polyhedral Graph, Quartic Nonhamiltonian Graph, Quintic Nonhamiltonian Graph, Tait's Hamiltonian Graph Conjecture

Explore with Wolfram|Alpha

References

Sloane, N. J. A. Sequence A007033/M5351 in "The On-Line Encyclopedia of Integer Sequences."Tait, P. G. "Remarks on the Colouring of Maps." Proc. Royal Soc. Edinburgh 10, 729, 1880.Tutte, W. T. "On Hamiltonian Circuits." J. London Math. Soc. 21, 98-101, 1946.Tutte, W. T. "Non-Hamiltonian Planar Maps." In Graph Theory and Computing (Ed. R. Read). New York: Academic Press, pp. 295-301, 1972.

Cite this as:

Weisstein, Eric W. "Polyhedral Nonhamiltonian Graph." From MathWorld--A Wolfram Web Resource. https://mathworld.wolfram.com/PolyhedralNonhamiltonianGraph.html

Subject classifications