Meredith graph
Introduction 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 .
Gallery Image:Meredith graph 3COL.svg|The chromatic number of the Meredith graph is 3.Image:Meredith graph 5color edge.svg|The chromatic index of the Meredith graph is 5.
References