TOPICS
Search

Tutte's Graph

DOWNLOAD Mathematica NotebookDownload Wolfram Notebook
TuttesGraph

Tutte's (46-vertex) graph is a cubic nonhamiltonian graph contructed by Tutte (1946) as a counterexample to Tait's Hamiltonian graph conjecture by using three copies ofTutte's fragment (Grünbaum 2003, pp. 359-360, Fig. 17.1.4).

A simpler counterexample to the Tutte 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 C_3 cyclic group graph.

Tutte's graph is implemented in the Wolfram Language as GraphData["TutteGraph"].

TuttesGraphMatrices

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's Fragment

Explore with Wolfram|Alpha

References

Berge, C. Graphs and Hypergraphs. New York: Elsevier, 1973.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.Read, R. C. and Wilson, R. J. An Atlas of Graphs. Oxford, England: Oxford University Press, p. 274, 1998.Royle, G. "Cubic Cages." http://school.maths.uwa.edu.au/~gordon/remote/cages/.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. 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.

Referenced on Wolfram|Alpha

Tutte's Graph

Cite this as:

Weisstein, Eric W. "Tutte's Graph." From MathWorld--A Wolfram Resource. https://mathworld.wolfram.com/TuttesGraph.html

Subject classifications