Tietze's graph

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. 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. Tietze's graph may be formed from the Petersen graph by replacing one of its vertices with a triangle. Like the Tietze graph, the Petersen graph forms the boundary of six mutually touching regions, but on the projective plane rather than on the Möbius strip. If one cuts a hole from this subdivision of the projective plane, surrounding a single vertex, the surrounded vertex is replaced by a triangle of region boundaries around the hole, giving the previously described construction of the Tietze graph. Both Tietze's graph and the Petersen graph are maximally nonhamiltonian: they have no Hamiltonian cycle, but any two non-adjacent vertices can be connected by a Hamiltonian path. Tietze's graph and the Petersen graph are the only 2-vertex-connected cubic non-Hamiltonian graphs with 12 or fewer vertices. Unlike the Petersen graph, Tietze's graph is not hypohamiltonian: removing one of its three triangle vertices forms a smaller graph that remains non-Hamiltonian. Edge coloring Tietze's graph requires four colors; that is, its chromatic index is 4. Equivalently, the edges of Tietze's graph can be partitioned into four matchings, but no fewer. Tietze's graph matches part of the definition of a snark: it is a cubic bridgeless graph that is not 3-edge-colorable. However, most authors restrict snarks to graphs without 3-cycles, so Tietze's graph is not generally considered to be a snark.