Tietze's graph

Tietze's subdivision of a Möbius strip into six mutually-adjacent regions. The vertices and edges of the subdivision form an embedding of Tietze's graph onto the strip.
Tietze's graph
The Tietze graph
Vertices12
Edges18
Radius3
Diameter3
Girth3
Automorphisms12 (D6)
Chromatic number3
Chromatic index4
PropertiesCubic
Snark
Table of graphs and parameters

In the mathematical field of graph theory, Tietze's graph is an undirected cubic graph with 12 vertices and 18 edges. It is named after Heinrich Franz Friedrich Tietze, who showed in 1910 that the Möbius strip can be subdivided into six regions that all touch each other – three along the boundary of the strip and three along its center line – and therefore that graphs that are embedded onto the Möbius strip may require six colors.[1] The boundary segments of the regions of Tietze's subdivision (including the segments along the boundary of the Möbius strip itself) form an embedding of Tietze's graph.

  1. ^ Tietze, Heinrich (1910), "Einige Bemerkungen zum Problem des Kartenfärbens auf einseitigen Flächen" [Some remarks on the problem of map coloring on one-sided surfaces] (PDF), DMV Annual Report, 19: 155–159