Tutte Graph on:
[Wikipedia]
[Google]
[Amazon]
In the
From a small planar graph called the Tutte fragment, W. T. Tutte 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, 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.
mathematical
Mathematics is a field of study that discovers and organizes methods, Mathematical theory, theories and theorems that are developed and Mathematical proof, proved for the needs of empirical sciences and mathematics itself. There are many ar ...
field of graph theory
In mathematics and computer science, graph theory is the study of ''graph (discrete mathematics), graphs'', which are mathematical structures used to model pairwise relations between objects. A graph in this context is made up of ''Vertex (graph ...
, the Tutte graph is a 3-regular graph
In graph theory, a regular graph is a Graph (discrete mathematics), graph where each Vertex (graph theory), vertex has the same number of neighbors; i.e. every vertex has the same Degree (graph theory), degree or valency. A regular directed graph ...
with 46 vertices and 69 edges named after W. T. Tutte. It has chromatic number
In graph theory, graph coloring is a methodic assignment of labels traditionally called "colors" to elements of a graph. The assignment is subject to certain constraints, such as that no two adjacent elements have the same color. Graph coloring i ...
3, chromatic index 3, girth 4 and diameter 8.
The Tutte graph is a cubic
Cubic may refer to:
Science and mathematics
* Cube (algebra), "cubic" measurement
* Cube, a three-dimensional solid object bounded by six square faces, facets or sides, with three meeting at each vertex
** Cubic crystal system, a crystal system w ...
polyhedral graph
In geometric graph theory, a branch of mathematics, a polyhedral graph is the undirected graph formed from the Vertex (geometry), vertices and Edge (geometry), edges of a convex polyhedron. Alternatively, in purely graph-theoretic terms, the polyh ...
, 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 K-vertex-connected graph, 3-connected Planar graph, planar cubic graph has a Hamiltonian cycle (along the edges) through all its Vertex (geometry), vertices". It was proposed by and disproved b ...
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.
Construction
From a small planar graph called the Tutte fragment, W. T. Tutte 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, 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, thecyclic group
In abstract algebra, a cyclic group or monogenous group is a Group (mathematics), group, denoted C_n (also frequently \Z_n or Z_n, not to be confused with the commutative ring of P-adic number, -adic numbers), that is Generating set of a group, ge ...
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 ...
of the Tutte graph is :
:
:
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 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 by the same fragment used in Tutte's example..References
{{reflist Individual graphs Regular graphs Planar graphs Hamiltonian paths and cycles