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

, the Tutte graph is a 3-

regular graph In graph theory, a regular graph is a graph where each vertex has the same number of neighbors; i.e. every vertex has the same degree or valency. A regular directed graph must also satisfy the stronger condition that the indegree and outdegree o ...

with 46 vertices and 69 edges named after

W. T. Tutte William Thomas Tutte OC FRS FRSC (; 14 May 1917 – 2 May 2002) was an English and Canadian codebreaker and mathematician. During the Second World War, he made a brilliant and fundamental advance in cryptanalysis of the Lorenz cipher, a majo ...

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

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

3, girth 4 and diameter 8. The Tutte graph is a cubic

polyhedral graph In geometric graph theory, a branch of mathematics, a polyhedral graph is the undirected graph formed from the vertices and edges of a convex polyhedron. Alternatively, in purely graph-theoretic terms, the polyhedral graphs are the 3-vertex-con ...

, but is non-

hamiltonian Hamiltonian may refer to: * Hamiltonian mechanics, a function that represents the total energy of a system * Hamiltonian (quantum mechanics), an operator corresponding to the total energy of that system ** Dyall Hamiltonian, a modified Hamiltonian ...

. Therefore, it is a counterexample to

Tait's conjecture In mathematics, Tait's conjecture states that "Every 3-connected planar cubic graph has a Hamiltonian cycle (along the edges) through all its vertices". It was proposed by and disproved by , who constructed a counterexample with 25 faces, 69 ed ...

that every 3-regular polyhedron has a Hamiltonian cycle. Published by Tutte in 1946, it is the first counterexample constructed for this conjecture. Other counterexamples were found later, in many cases based on

Grinberg's theorem In graph theory, Grinberg's theorem is a necessary condition for a planar graph to contain a Hamiltonian cycle, based on the lengths of its face cycles. If a graph does not meet this condition, it is not Hamiltonian. The result has been widely us ...

Construction

From a small planar graph called the Tutte fragment,

constructed a non-Hamiltonian polyhedron, by putting together three such fragments. The "compulsory" edges of the fragments, that must be part of any Hamiltonian path through the fragment, are connected at the central vertex; because any cycle can use only two of these three edges, there can be no Hamiltonian cycle. The resulting graph is 3-connected and

planar Planar is an adjective meaning "relating to a plane (geometry)". Planar may also refer to: Science and technology * Planar (computer graphics), computer graphics pixel information from several bitplanes * Planar (transmission line technologies), ...

, so by Steinitz' theorem it is the graph of a polyhedron. It has 25 faces. It can be realized geometrically from a tetrahedron (the faces of which correspond to the four large nine-sided faces in the drawing, three of which are between pairs of fragments and the fourth of which forms the exterior) by multiply truncating three of its vertices.

Algebraic properties

The automorphism group of the Tutte graph is Z/3Z, the

cyclic group In group theory, a branch of abstract algebra in pure mathematics, a cyclic group or monogenous group is a group, denoted C''n'', that is generated by a single element. That is, it is a set of invertible elements with a single associative bina ...

of order 3. 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 chara ...

of the Tutte graph is : :

(x-3)(x^-22x^+x^+184x^-26x^-731x^9+199x^8+1383x^7-576x^6-1061x^5+561x^4+233x^3-151x^2+4x+4)^2

(x^+3x^-16x^-50x^+94x^+310x^-257x^9-893x^8+366x^7+1218x^6-347x^5-717x^4+236x^3+128x^2-56x+4).

Related graphs

Although the Tutte graph is the first 3-regular non-Hamiltonian polyhedral graph to be discovered, it is not the smallest such graph. In 1965 Lederberg found the

Barnette–Bosák–Lederberg graph In the mathematics, mathematical field of graph theory, the Barnette–Bosák–Lederberg graph is a cubic graph, cubic (that is, 3-regular graph, regular) polyhedral graph with no Hamiltonian cycle, the smallest such graph possible. It was discov ...

on 38 vertices. In 1968, Grinberg constructed additional small counterexamples to the Tait's conjecture – the Grinberg graphs on 42, 44 and 46 vertices. In 1974 Faulkner and Younger published two more graphs – the Faulkner–Younger graphs on 42 and 44 vertices. Finally Holton and McKay showed there are exactly six 38-vertex non-Hamiltonian polyhedra that have nontrivial three-edge cuts. They are formed by replacing two of the vertices of a

pentagonal prism In geometry, the pentagonal prism is a prism with a pentagonal base. It is a type of heptahedron with seven faces, fifteen edges, and ten vertices. As a semiregular (or uniform) polyhedron If faces are all regular, the pentagonal prism is ...

by the same fragment used in Tutte's example..

References

{{reflist Individual graphs Regular graphs Planar graphs Hamiltonian paths and cycles