The Tutte graph is a 46-vertex cubic nonhamiltonian graph constructed by Tutte (1946) as a counterexample
to Tait's Hamiltonian graph conjecture
by using three copies of the Tutte fragment (Grünbaum
2003, pp. 359-360, Fig. 17.1.4).
A simpler counterexample to Tait's Hamiltonian graph conjecture was later given by Kozyrev and Grinberg (Sachs 1968,
Berge 1973), and smaller counterexamples include
the Barnette-Bosák-Lederberg
graph, Faulkner-Younger graphs, Grinberg graphs, and Grünbaum
graphs.
Tutte's graph is a 
cyclic group graph.
Tutte's graph is implemented in the Wolfram
Language as GraphData["TutteGraph"].
The plots above show the adjacency, incidence,
and graph distance matrices for Tutte's graph.
The Tutte 8-cage is sometimes also called the Tutte
graph (Royle).
See also
Barnette-Bosák-Lederberg Graph,
Faulkner-Younger Graphs,
Grinberg Graphs,
Grünbaum
Graphs,
Hamiltonian Cycle,
Nonhamiltonian
Graph,
Tait's Hamiltonian Graph
Conjecture,
Tutte 8-Cage,
Tutte
12-Cage,
Tutte Fragment
Explore with Wolfram|Alpha
References
Berge, C. Graphs and Hypergraphs. New York: Elsevier, 1973.Bondy, J. A.
and Murty, U. S. R. Graph
Theory. Berlin, Germany: Springer-Verlag, p. 478, 2008.Grünbaum,
B. Convex
Polytopes, 2nd ed. New York: Springer-Verlag, 2003.Honsberger,
R. Mathematical
Gems I. Washington, DC: Math. Assoc. Amer., pp. 82-89, 1973.House
of Graphs. "Tutte Graph." https://houseofgraphs.org/graphs/1399.Read,
R. C. and Wilson, R. J. An
Atlas of Graphs. Oxford, England: Oxford University Press, p. 274, 1998.Royle,
G. "Cubic Cages." https://web.archive.org/web/20060823134140/http://people.csse.uwa.edu.au/gordon/cages/index.html.Saaty,
T. L. and Kainen, P. C. The
Four-Color Problem: Assaults and Conquest. New York: Dover, p. 112,
1986.Sachs, H. "Ein von Kozyrev und Grinberg angegebener nicht-Hamiltonischer
kubischer planarer Graph." In Beiträge zur Graphentheorie (Ed. H. Sachs,
H.-J. Voß, and H. Walther). Leipzig, Germany: Teubner, pp. 127-130,
1968.Skiena, S. Implementing
Discrete Mathematics: Combinatorics and Graph Theory with Mathematica. Reading,
MA: Addison-Wesley, p. 198, 1990.Tait, P. G. "Remarks
on the Colouring of Maps." Proc. Royal Soc. Edinburgh 10, 729,
1880.Tutte, W. T. "On Hamiltonian Circuits." J. London
Math. Soc. 21, 98-101, 1946.Tutte, W. T. "Non-Hamiltonian
Planar Maps." In Graph
Theory and Computing (Ed. R. Read). New York: Academic Press, pp. 295-301,
1972.
Cite this as:
Weisstein, Eric W. "Tutte Graph." From
MathWorld--A Wolfram Resource. https://mathworld.wolfram.com/TutteGraph.html
Subject classifications
