Meredith graph
≈ 2 min read
Names in other languages
No names in other languages are held for this entry yet.
Article bodies are English and are not machine-translated. A name in another language is not a translation of the article.
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 19731. 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-26 x^4+3 x^3+169 x^2-39 x-45)^4 .
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-26 x^4+3 x^3+169 x^2-39 x-45)^4 .
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.
Text derived from https://en.wikipedia.org/w/index.php?oldid=1236309102 under CC BY-SA 4.0; modifications have been made.