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.^[1]

Named afterG. H. Meredith

Vertices70

Edges140

Radius7

Quick facts Named after, Vertices ...

Meredith graph
The Meredith graph
Named after	G. H. Meredith
Vertices	70
Edges	140
Radius	7
Diameter	8
Girth	4
Automorphisms	38698352640
Chromatic number	3
Chromatic index	5
Book thickness	3
Queue number	2
Properties	Eulerian
Table of graphs and parameters

Close

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 ${\displaystyle (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}}$.