Meredith graph
4-regular undirected graph with 70 vertices and 140 edges
title: "Meredith graph" type: doc version: 1 created: 2026-02-28 author: "Wikipedia contributors" status: active scope: public tags: ["individual-graphs", "regular-graphs"] description: "4-regular undirected graph with 70 vertices and 140 edges" topic_path: "general/individual-graphs" source: "https://en.wikipedia.org/wiki/Meredith_graph" license: "CC BY-SA 4.0" wikipedia_page_id: 0 wikipedia_revision_id: 0
::summary 4-regular undirected graph with 70 vertices and 140 edges ::
::data[format=table title="infobox graph"]
| Field | Value |
|---|---|
| name | Meredith graph |
| image | [[Image:Meredith graph.svg |
| 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 |
| :: |
| name = Meredith graph | image = [[Image:Meredith graph.svg|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.
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.{{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 n-valent n-connected nonHamiltonian non-n-edge-colorable graphs | volume = 14 | year = 1973| doi-access = free
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.
References
References
- "Meredith graph".
- 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
- 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.
::callout[type=info title="Wikipedia Source"] This article was imported from Wikipedia and is available under the Creative Commons Attribution-ShareAlike 4.0 License. Content has been adapted to SurfDoc format. Original contributors can be found on the article history page. ::