In the

mathematical Mathematics is an area of knowledge that includes the topics of numbers, formulas and related structures, shapes and the spaces in which they are contained, and quantities and their changes. These topics are represented in modern mathematics ...

field of

graph theory In mathematics, graph theory is the study of '' graphs'', which are mathematical structures used to model pairwise relations between objects. A graph in this context is made up of '' vertices'' (also called ''nodes'' or ''points'') which are conn ...

, 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 '' ...

cubic graph In the mathematical field of graph theory, a cubic graph is a graph in which all vertices have degree three. In other words, a cubic graph is a 3-regular graph. Cubic graphs are also called trivalent graphs. A bicubic graph is a cubic bipa ...

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 transfo ...

, 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 A ...

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 Embedded or embedding (alternatively imbedded or imbedding) may refer to: Science * Embedding, in mathematics, one instance of some mathematical object contained within another instance ** Graph embedding * Embedded generation, a distributed ge ...

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 In the mathematics, mathematical field of graph theory, the Petersen graph is an undirected graph with 10 vertex (graph theory), vertices and 15 edge (graph theory), edges. It is a small graph that serves as a useful example and counterexample for ...

by replacing one of its vertices with a

triangle A triangle is a polygon with three edges and three vertices. It is one of the basic shapes in geometry. A triangle with vertices ''A'', ''B'', and ''C'' is denoted \triangle ABC. In Euclidean geometry, any three points, when non- colli ...

. Like the Tietze graph, the Petersen graph forms the boundary of six mutually touching regions, but on the

projective plane In mathematics, a projective plane is a geometric structure that extends the concept of a plane. In the ordinary Euclidean plane, two lines typically intersect in a single point, but there are some pairs of lines (namely, parallel lines) that ...

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 In the mathematical field of graph theory, a Hamiltonian path (or traceable path) is a path in an undirected or directed graph that visits each vertex exactly once. A Hamiltonian cycle (or Hamiltonian circuit) is a cycle that visits each vertex ...

, 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 In graph theory, an edge coloring of a graph is an assignment of "colors" to the edges of the graph so that no two incident edges have the same color. For example, the figure to the right shows an edge coloring of a graph by the colors red, blue ...

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. 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 flowe ...

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 In computational complexity theory, a problem is NP-complete when: # it is a problem for which the correctness of each solution can be verified quickly (namely, in polynomial time) and a brute-force search algorithm can find a solution by tryin ...

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 In mathematics, the automorphism group of an object ''X'' is the group consisting of automorphisms of ''X'' under composition of morphisms. For example, if ''X'' is a finite-dimensional vector space, then the automorphism group of ''X'' is th ...

has order 12, and is isomorphic to the

dihedral group In mathematics, a dihedral group is the group of symmetries of a regular polygon, which includes rotations and reflections. Dihedral groups are among the simplest examples of finite groups, and they play an important role in group theory, ...

D₆, the group of symmetries of a

hexagon In geometry, a hexagon (from Greek , , meaning "six", and , , meaning "corner, angle") is a six-sided polygon. The total of the internal angles of any simple (non-self-intersecting) hexagon is 720°. Regular hexagon A ''regular hexagon'' h ...

, 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 fa ...

Gallery

File:Tietze's graph 3COL.svg, The

chromatic number In graph theory, graph coloring is a special case of graph labeling; it is an assignment of labels traditionally called "colors" to elements of a graph subject to certain constraints. In its simplest form, it is a way of coloring the vertices o ...

of the Tietze graph is 3. File:Tietze's graph 4color edge.svg, The

chromatic index In graph theory, an edge coloring of a graph is an assignment of "colors" to the edges of the graph so that no two incident edges have the same color. For example, the figure to the right shows an edge coloring of a graph by the colors red, blue ...

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