4-regular undirected graph with 70 vertices and 140 edges
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] 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] W. T. Tutte showed that all 4-connected planar graphs are hamiltonian.[ 6]
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
{\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}}
Gallery
References
^ Weisstein, Eric W. "Meredith graph" . MathWorld ^ Bondy, J. A. and Murty, U. S. R. "Graph Theory". Springer, p. 470, 2007.
^ Jessica Wolz, Engineering Linear Layouts with SAT . Master Thesis, University of Tübingen, 2018
^ Meredith, G. H. J. (1973). "Regular n -valent n -connected nonHamiltonian non-n -edge-colorable graphs" . Journal of Combinatorial Theory, Series B . 14 : 55– 60. doi :10.1016/s0095-8956(73)80006-1 MR 0311503 . ^ Bondy, J. A. and Murty, U. S. R. "Graph Theory with Applications". New York: North Holland, p. 239, 1976.
^ Tutte, W.T., ed., Recent Progress in Combinatorics. Academic Press, New York, 1969.
