Math gifts

- Art Gallery -

In the mathematical field of graph theory, the Meredith graph is a 4-regular undirected graph with 70 vertices and 140 edges discovered by Guy H. J. Meredith in 1973.[1]

Meredith graph

The Meredith graph is 4-vertex-connected and 4-edge-connected, has chromatic number 3, chromatic index 5, radius 7, diameter 8, girth 4 and is non-hamiltonian.[2] It has book thickness 3 and queue number 2.[3]

Published in 1973, it provides a counterexample to the Crispin Nash-Williams conjecture that every 4-regular 4-vertex-connected graph is Hamiltonian.[4][5] However, W. T. Tutte showed that all 4-connected planar graphs are hamiltonian.[6]

The characteristic polynomial of the Meredith graph is \( (x-4)(x-1)^{{10}}x^{{21}}(x+1)^{{11}}(x+3)(x^{2}-13)(x^{6}-26x^{4}+3x^{3}+169x^{2}-39x-45)^{4} \).



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 4-Valent 4-Connected Nonhamiltonian Non-4-Edge-Colorable Graphs." J. Combin. Th. B 14, 55-60, 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 Texts in Mathematics

Graduate Studies in Mathematics

Mathematics Encyclopedia



Hellenica World - Scientific Library

Retrieved from ""
All text is available under the terms of the GNU Free Documentation License