Meredith Graph


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.


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


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.

Subject classifications