Meredith graph

Meredith graph The Meredith graph
Named afterG. H. Meredith
Vertices70
Edges140
Diameter8
Girth4
Automorphisms38698352640
Chromatic number3
Chromatic index5
Book thickness3
Queue number2
PropertiesEulerian
Table of graphs and parameters

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. It has book thickness 3 and queue number 2.

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}-26x^{4}+3x^{3}+169x^{2}-39x-45)^{4}$ .