In the mathematical field of graph theory, Tietze's graph is an

undirected In discrete mathematics, and more specifically in graph theory, a graph is a structure amounting to a set of objects in which some pairs of the objects are in some sense "related". The objects correspond to mathematical abstractions called '' v ...

cubic graph with 12 vertices and 18 edges. It is named after

Heinrich Franz Friedrich Tietze Heinrich Franz Friedrich Tietze (August 31, 1880 – February 17, 1964) was an Austrian mathematician, famous for the Tietze extension theorem on functions from topological spaces to the real numbers. He also developed the Tietze transformat ...

, who showed in 1910 that the

Möbius strip In mathematics, a Möbius strip, Möbius band, or Möbius loop is a surface that can be formed by attaching the ends of a strip of paper together with a half-twist. As a mathematical object, it was discovered by Johann Benedict Listing and Augu ...

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.

Relation to Petersen 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.

Hamiltonicity

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 and perfect matchings

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 In graph theory, a bridge, isthmus, cut-edge, or cut arc is an edge of a graph whose deletion increases the graph's number of connected components. Equivalently, an edge is a bridge if and only if it is not contained in any cycle. For a connec ...

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. Nevertheless, it is isomorphic to the graph J₃, part of an infinite family of

flower snark In the mathematical field of graph theory, the flower snarks form an infinite family of snarks introduced by Rufus Isaacs in 1975. As snarks, the flower snarks are connected, bridgeless cubic graphs with chromatic index equal to 4. The flower ...

s introduced by R. Isaacs in 1975. Unlike the Petersen graph, the Tietze graph can be covered by four

perfect matching In graph theory, a perfect matching in a graph is a matching that covers every vertex of the graph. More formally, given a graph , a perfect matching in is a subset of edge set , such that every vertex in the vertex set is adjacent to exactly ...

s. This property plays a key role in a proof that testing whether a graph can be covered by four perfect matchings is NP-complete..

Additional properties

Tietze's graph has chromatic number 3, chromatic index 4, girth 3 and diameter 3. The

independence number Independence is a condition of a person, nation, country, or Sovereign state, state in which residents and population, or some portion thereof, exercise self-government, and usually sovereignty, over its territory. The opposite of independ ...

is 5. Its automorphism group has order 12, and is isomorphic to the dihedral group D₆, the group of symmetries of a hexagon, including both rotations and reflections. This group has two orbits of size 3 and one of size 6 on vertices, and thus this graph is not

vertex-transitive In geometry, a polytope (e.g. a polygon or polyhedron) or a tiling is isogonal or vertex-transitive if all its vertices are equivalent under the symmetries of the figure. This implies that each vertex is surrounded by the same kinds of face in ...

Gallery

File:Tietze's graph 3COL.svg, The chromatic number of the Tietze graph is 3. File:Tietze's graph 4color edge.svg, The chromatic index of the Tietze graph is 4. File:Tietze-2crossings.svg, The Tietze graph has crossing number 2 and is 1-planar. File:Y12W129EE4170908.jpg, A three-dimensional embedding of the Tietze graph.

Notes