TOPICS

Tietze's Graph

DOWNLOAD Mathematica NotebookDownload Wolfram Notebook
TietzesGraphEmbeddings

Tietze's graph is the cubic graph on 12 nodes and 18 edges, illustrated above in a number of embeddings.

It is implemented in the Wolfram Language as GraphData["TietzeGraph"].

Tietze's graph is the unique almost Hamiltonian cubic graph on 12 vertices (Punnim et al. 2007). In fact, it is also maximally nonhamiltonian (Clark and Entringer 1983).

TietzeMoebiusColoring

Tietze's graph provides a 6-color coloring of the Möbius strip as illustrated above (Bondy and Murty 1976, p. 243).

TietzeGraphMatrices

The plots above show the adjacency, incidence, and graph distance matrices for Tietze's graph.

See also

Cubic Graph, Möbius Strip

Explore with Wolfram|Alpha

References

Bondy, J. A. and Murty, U. S. R. Graph Theory with Applications. New York: North Holland, p. 243, 1976.Clark, L. and Entringer, R. "Smallest Maximally Nonhamiltonian Graphs." Periodica Math. Hungarica 14, 57-68, 1983.Punnim, N.; Saenpholphat, V.; and Thaithae, S. "Almost Hamiltonian Cubic Graphs." Int. J. Comput. Sci. Netw. Security 7, 83-86, 2007.

Referenced on Wolfram|Alpha

Tietze's Graph

Cite this as:

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

Subject classifications