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. 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 formula_1.
Q395
mathematical
Concept
Q131476
graph theory
Concept
Q826467
regular
Concept
Q141488
undirected graph
Concept
Q3115621
vertex-connected
Concept
Q3034655
edge-connected
Concept
Q504843
chromatic number
Concept
Q1050972
chromatic index
Concept
Q273037
non-hamiltonian
Concept
Q4942980
book thickness
UNK
Q25303837
queue number
UNK
Q3002796
Crispin Nash-Williams
PER
Q1391861
W. T. Tutte
PER
Q547823
planar graph
Concept
Q849705
characteristic polynomial
Concept
Q3115517
Meredith graph
Concept
Q3115517
Meredith graph
Concept
Q3115517
Meredith graph
Concept
1973-01-01T00:00:00Z^^http://www.w3.org/2001/XMLSchema#dateTime
1973
DATE
1973-01-01T00:00:00Z^^http://www.w3.org/2001/XMLSchema#dateTime
1973
DATE
+4^^http://www.w3.org/2001/XMLSchema#decimal
4
NUMBER
+70^^http://www.w3.org/2001/XMLSchema#decimal
70
NUMBER
+4^^http://www.w3.org/2001/XMLSchema#decimal
4
NUMBER
+4^^http://www.w3.org/2001/XMLSchema#decimal
4
NUMBER
+3^^http://www.w3.org/2001/XMLSchema#decimal
3
NUMBER
+5^^http://www.w3.org/2001/XMLSchema#decimal
5
NUMBER
+7^^http://www.w3.org/2001/XMLSchema#decimal
7
NUMBER
+8^^http://www.w3.org/2001/XMLSchema#decimal
8
NUMBER
+4^^http://www.w3.org/2001/XMLSchema#decimal
4
NUMBER
+3^^http://www.w3.org/2001/XMLSchema#decimal
3
NUMBER
+2^^http://www.w3.org/2001/XMLSchema#decimal
2
NUMBER
+4^^http://www.w3.org/2001/XMLSchema#decimal
4
NUMBER
+4^^http://www.w3.org/2001/XMLSchema#decimal
4
NUMBER
+4^^http://www.w3.org/2001/XMLSchema#decimal
4
NUMBER
+1^^http://www.w3.org/2001/XMLSchema#decimal
1
NUMBER
studies
instance of
instance of
part of
studies