In the mathematical field of graph theory, the Meredith graph is a 4regular undirected graph with 70 vertices and 140 edges discovered by Guy H. J. Meredith in 1973.[1]
The Meredith graph is 4vertexconnected and 4edgeconnected, has chromatic number 3, chromatic index 5, radius 7, diameter 8, girth 4 and is nonhamiltonian.[2] It has book thickness 3 and queue number 2.[3]
Published in 1973, it provides a counterexample to the Crispin NashWilliams conjecture that every 4regular 4vertexconnected graph is Hamiltonian.[4][5] However, W. T. Tutte showed that all 4connected planar graphs are hamiltonian.[6]
The characteristic polynomial of the Meredith graph is \( (x4)(x1)^{{10}}x^{{21}}(x+1)^{{11}}(x+3)(x^{2}13)(x^{6}26x^{4}+3x^{3}+169x^{2}39x45)^{4} \).
Gallery

The chromatic number of the Meredith graph is 3.

The chromatic index of the Meredith graph is 5.
References
Weisstein, Eric W. "Meredith graph". MathWorld.
Bondy, J. A. and Murty, U. S. R. "Graph Theory". Springer, p. 470, 2007.
Jessica Wolz, Engineering Linear Layouts with SAT. Master Thesis, University of Tübingen, 2018
Meredith, G. H. J. "Regular 4Valent 4Connected Nonhamiltonian Non4EdgeColorable Graphs." J. Combin. Th. B 14, 5560, 1973.
Bondy, J. A. and Murty, U. S. R. "Graph Theory with Applications". New York: North Holland, p. 239, 1976.
Tutte, W.T., ed., Recent Progress in Combinatorics. Academic Press, New York, 1969.
Undergraduate Texts in Mathematics
Graduate Studies in Mathematics
Hellenica World  Scientific Library
Retrieved from "http://en.wikipedia.org/"
All text is available under the terms of the GNU Free Documentation License