TOPICS
Search

Georges Graph

DOWNLOAD Mathematica NotebookDownload Wolfram Notebook
GeorgesGraph

The Georges graph, also called the Georges-Kel'mans graph, is the 50-node graph illustrated above that is the smallest 3-connected bicubic nonhamiltonian graph. It was independently discovered by Georges (1989) and Kelmans (1988) as the smallest known such example. It was subsequently proved to be the smallest possible by Brinkmann et al. (2022).

It is implemented in the Wolfram Language as GraphData["GeorgesGraph"].

GeorgesGraphGruenbaum

The original embedding showing the construction is illustrated above (Grünbaum 2006).

See also

Bicubic Graph, Bicubic Nonhamiltonian Graph, Nonhamiltonian Graph

Explore with Wolfram|Alpha

References

Bondy, J. A. and Murty, U. S. R. Graph Theory. Berlin: Springer-Verlag, pp. 487-488, 2008.Brinkmann, G.; Goedgebeur, J.; and McKay, B. D. "the Minimality of the Georges-Kelmans Graph." Math. Comput. 91, 1483-1500, 2022.Georges, J. P. "Non-Hamiltonian Bicubic Graphs." J. Combin. Th. B 46, 121-124, 1989.Grünbaum, B. "3-Connected Configurations (n_3) with No Hamiltonian Circuit." Bull. Inst. Combin. Appl. 46, 15-26, 2006.Grünbaum, B. Configurations of Points and Lines. Providence, RI: Amer. Math. Soc., p. 311, 2009.Kel'mans, A. K. "Cubic Bipartite Cyclically-Connected Graphs With No Hamiltonian Cycles." Uspekhi Mat. Nauk 43, 181-182, 1988. English transl. in Russian Math. Surveys 43, 205-206, 1988.

Cite this as:

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

Subject classifications