TOPICS
Search

Meredith Graph

DOWNLOAD Mathematica NotebookDownload Wolfram Notebook
MeredithGraph

The Meredith graph is a quartic nonhamiltonian graph on 70 nodes and 140 edges that is a counterexample to the conjecture that every 4-regular 4-connected graph is Hamiltonian.

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

The Meredith graph has chromatic number 3 and edge chromatic number 5.

MeredithGraphMatrices

The plots above show the adjacency, incidence, and distance matrices of the graph.

See also

Hamiltonian Graph, Quartic Graph, Quartic Nonhamiltonian Graph

Explore with Wolfram|Alpha

References

Bondy, J. A. and Murty, U. S. R. Graph Theory with Applications. New York: North Holland, pp. 236-239, 1976.Bondy, J. A. and Murty, U. S. R. Graph Theory. Berlin: Springer-Verlag, p. 407, 2008.Holton, D. A. and Sheehan, J. The Petersen Graph. Cambridge, England: Cambridge University Press, p. 103-104, 1993.Meredith, G. H. J. "Regular n-Valent n-Connected Nonhamiltonian Non-n-Edge-Colorable Graphs." J. Combin. Th. B 14, 55-60, 1973.

Cite this as:

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

Subject classifications