Meredith graph

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.

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.

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

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 − 26 x 4 + 3 x 3 + 169 x 2 − 39 x − 45 ) 4 .