In the
mathematical
Mathematics is an area of knowledge that includes the topics of numbers, formulas and related structures, shapes and the spaces in which they are contained, and quantities and their changes. These topics are represented in modern mathematics ...
field of
graph theory
In mathematics, graph theory is the study of '' graphs'', which are mathematical structures used to model pairwise relations between objects. A graph in this context is made up of '' vertices'' (also called ''nodes'' or ''points'') which are conn ...
, the Meredith graph is a 4-
regular
The term regular can mean normal or in accordance with rules. It may refer to:
People
* Moses Regular (born 1971), America football player
Arts, entertainment, and media Music
* "Regular" (Badfinger song)
* Regular tunings of stringed instrum ...
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
In graph theory, graph coloring is a special case of graph labeling; it is an assignment of labels traditionally called "colors" to elements of a graph subject to certain constraints. In its simplest form, it is a way of coloring the vertices o ...
3,
chromatic index
In graph theory, an edge coloring of a graph is an assignment of "colors" to the edges of the graph so that no two incident edges have the same color. For example, the figure to the right shows an edge coloring of a graph by the colors red, blue ...
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 graph
In graph theory, a planar graph is a graph that can be embedded in the plane, i.e., it can be drawn on the plane in such a way that its edges intersect only at their endpoints. In other words, it can be drawn in such a way that no edges cro ...
s are hamiltonian.
[Tutte, W.T., ed., Recent Progress in Combinatorics. Academic Press, New York, 1969.]
The
characteristic polynomial
In linear algebra, the characteristic polynomial of a square matrix is a polynomial which is invariant under matrix similarity and has the eigenvalues as roots. It has the determinant and the trace of the matrix among its coefficients. The ...
of the Meredith graph is
.
Gallery
Image:Meredith graph 3COL.svg, The chromatic number
In graph theory, graph coloring is a special case of graph labeling; it is an assignment of labels traditionally called "colors" to elements of a graph subject to certain constraints. In its simplest form, it is a way of coloring the vertices o ...
of the Meredith graph is 3.
Image:Meredith graph 5color edge.svg, The chromatic index
In graph theory, an edge coloring of a graph is an assignment of "colors" to the edges of the graph so that no two incident edges have the same color. For example, the figure to the right shows an edge coloring of a graph by the colors red, blue ...
of the Meredith graph is 5.
References
{{reflist
Individual graphs
Regular graphs