Meredith graph

{{Short description|4-regular undirected graph with 70 vertices and 140 edges}}

{{infobox graph

| name = Meredith graph

| image = 220px

| image_caption = The Meredith graph

| namesake = G. H. Meredith

| vertices = 70

| edges = 140

| girth = 4

| diameter = 8

| radius = 7

| automorphisms = 38698352640

| chromatic_number = 3

| chromatic_index = 5

| properties = Eulerian

|book thickness=3|queue number=2}}

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.{{MathWorld|urlname=MeredithGraph|title=Meredith graph}}

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.Bondy, J. A. and Murty, U. S. R. "Graph Theory". Springer, p. 470, 2007. It has book thickness 3 and queue number 2.Jessica Wolz, Engineering Linear Layouts with SAT. Master Thesis, University of Tübingen, 2018

Published in 1973, it provides a counterexample to the Crispin Nash-Williams conjecture that every 4-regular 4-vertex-connected graph is Hamiltonian.{{cite journal

| last = Meredith | first = G. H. J.

| doi = 10.1016/s0095-8956(73)80006-1

| journal = Journal of Combinatorial Theory, Series B

| mr = 311503

| pages = 55–60

| title = Regular {{mvar|n}}-valent {{mvar|n}}-connected nonHamiltonian non-{{mvar|n}}-edge-colorable graphs

| volume = 14

| year = 1973| doi-access = free

}}Bondy, J. A. and Murty, U. S. R. "Graph Theory with Applications". New York: North Holland, p. 239, 1976. However, W. T. Tutte showed that all 4-connected planar graphs are hamiltonian.Tutte, W.T., ed., Recent Progress in Combinatorics. Academic Press, New York, 1969.

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