TOPICS
Search

Tutte's Fragment

DOWNLOAD Mathematica NotebookDownload Wolfram Notebook
TutteFragment

Tutte's fragment (Taylor 1997) is the 15-node graph illustrated above (Grünbaum 2003, pp. 358-359 and Fig. 17.1.3).

TutteFragmentPaths

If the graph obtained by adding pendant edges to corners of the triangle is part of a larger graph, then any Hamiltonian path through the graph must pass through the top vertex and one of of the lower two. Specifically, it is not possible for it to enter through one of the lower vertices and out the other (Taylor 1997). Tutte (1946) used this fact to join three Tutte fragments (at their tops and sides) into Tutte's graph, the first known counterexample to Tait's Hamiltonian graph conjecture.

Tutte's fragment is implemented in the Wolfram Language as GraphData["TutteFragment"].

See also

Tait's Hamiltonian Graph Conjecture, Tutte's Graph, Walther Graphs

Explore with Wolfram|Alpha

References

Grünbaum, B. Convex Polytopes, 2nd ed. New York: Springer-Verlag, p. 357, 2003.Harary, F. Problem 2.10 in Graph Theory. Reading, MA: Addison-Wesley, p. 24, 1994.Taylor, B. "Tutte's Fragment. An Adventure in Graph Theory." sci.math posting. Oct. 6, 1997.Tutte, W. T. "On Hamiltonian Circuits." J. London Math. Soc. 21, 98-101, 1946.

Cite this as:

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

Subject classifications