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 |
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]
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 .