WikiMili The Free Encyclopedia

Tietze's graph | |
---|---|

The Tietze graph | |

Vertices | 12 |

Edges | 18 |

Radius | 3 |

Diameter | 3 |

Girth | 3 |

Automorphisms | 12 (D_{6}) |

Chromatic number | 3 |

Chromatic index | 4 |

Properties | Cubic 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.

**Mathematics** includes the study of such topics as quantity, structure, space, and change.

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*, *nodes*, or *points* which are connected by *edges*, *arcs*, or *lines*. A graph may be *undirected*, meaning that there is no distinction between the two vertices associated with each edge, or its edges may be *directed* from one vertex to another; see Graph for more detailed definitions and for other variations in the types of graph that are commonly considered. Graphs are one of the prime objects of study in discrete mathematics.

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

Tietze's graph may be formed from the Petersen graph by replacing one of its vertices with a triangle.^{ [2] }^{ [3] } 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.

In the mathematical field of graph theory, the **Petersen graph** is an undirected graph with 10 vertices and 15 edges. It is a small graph that serves as a useful example and counterexample for many problems in graph theory. The Petersen graph is named after Julius Petersen, who in 1898 constructed it to be the smallest bridgeless cubic graph with no three-edge-coloring.

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 .

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 that do not intersect. A projective plane can be thought of as an ordinary plane equipped with additional "points at infinity" where parallel lines intersect. Thus *any* two distinct lines in a projective plane intersect in one and only one point.

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.^{ [2] } Tietze's graph and the Petersen graph are the only 2-vertex-connected cubic non-Hamiltonian graphs with 12 or fewer vertices.^{ [4] }

In graph theory, a connected graph *G* is said to be ** k-vertex-connected** if it has more than

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.

In the mathematical field of graph theory, a graph *G* is said to be **hypohamiltonian** if *G* does not itself have a Hamiltonian cycle but every graph formed by removing a single vertex from *G* is 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.

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, and green. Edge colorings are one of several different types of graph coloring. The **edge-coloring problem** asks whether it is possible to color the edges of a given graph using at most k different colors, for a given value of k, or with the fewest possible colors. The minimum required number of colors for the edges of a given graph is called the **chromatic index** of the graph. For example, the edges of the graph in the illustration can be colored by three colors but cannot be colored by two colors, so the graph shown has chromatic index three.

In the mathematical discipline of graph theory, a **matching** or **independent edge set** in a graph is a set of edges without common vertices. Finding a matching in a bipartite graph can be treated as a network flow problem.

Tietze's graph matches part of the definition of a snark: it is a cubic bridgeless graph that is not 3-edge-colorable. However, some authors restrict snarks to graphs without 3-cycles and 4-cycles, and under this more restrictive definition Tietze's graph is not a snark. Tietze's graph is isomorphic to the graph J_{3}, part of an infinite family of flower snarks introduced by R. Isaacs in 1975.^{ [5] }

In the mathematical field of graph theory, a **snark** is a simple, connected, bridgeless cubic graph with chromatic index equal to 4. In other words, it is a graph in which every vertex has three neighbors, the connectivity is redundant so that removing no one edge would split the graph, and the edges cannot be colored by only three colors without two edges of the same color meeting at a point. In order to avoid trivial cases, snarks are often restricted to have girth at least 5.

In the mathematical field of graph theory, the **flower snarks** form an infinite family of snarks introduced by Rufus Isaacs in 1975.

Unlike the Petersen graph, the Tietze graph can be covered by four perfect matchings. This property plays a key role in a proof that testing whether a graph can be covered by four perfect matchings is NP-complete.^{ [6] }

Tietze's graph has chromatic number 3, chromatic index 4, girth 3 and diameter 3. The independence number is 5. Its automorphism group has order 12, and is isomorphic to the dihedral group D_{6}, the group of symmetries of an 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.

- The chromatic number of the Tietze graph is 3.
- The chromatic index of the Tietze graph is 4.
- The Tietze graph has crossing number 2 and is 1-planar.
- A three-dimensional embedding of the Tietze graph.

Wikimedia Commons has media related to . Tietze's graph |

- Dürer graph and Franklin graph, two other 12-vertex cubic graphs

- ↑ 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],
*DMV Annual Report*,**19**: 155–159^{[ permanent dead link ]}. - 1 2 Clark, L.; Entringer, R. (1983), "Smallest maximally nonhamiltonian graphs",
*Periodica Mathematica Hungarica*,**14**(1): 57–68, doi:10.1007/BF02023582 - ↑ Weisstein, Eric W. "Tietze's Graph".
*MathWorld*. - ↑ Punnim, Narong; Saenpholphat, Varaporn; Thaithae, Sermsri (2007), "Almost Hamiltonian cubic graphs" (PDF),
*International Journal of Computer Science and Network Security*,**7**(1): 83–86 - ↑ Isaacs, R. (1975), "Infinite families of nontrivial trivalent graphs which are not Tait colorable",
*Amer. Math. Monthly*, Mathematical Association of America,**82**(3): 221–239, doi:10.2307/2319844, JSTOR 2319844 . - ↑ Esperet, L.; Mazzuoccolo, G. (2014), "On cubic bridgeless graphs whose edge-set cannot be covered by four perfect matchings",
*Journal of Graph Theory*,**77**(2): 144–157, arXiv: 1301.6926, doi:10.1002/jgt.21778, MR 3246172 .

This page is based on this Wikipedia article

Text is available under the CC BY-SA 4.0 license; additional terms may apply.

Images, videos and audio are available under their respective licenses.

Text is available under the CC BY-SA 4.0 license; additional terms may apply.

Images, videos and audio are available under their respective licenses.

This is a **glossary of graph theory terms**. Graph theory is the study of graphs, systems of nodes or vertices connected in pairs by edges.

In graph theory, an **outerplanar graph** is a graph that has a planar drawing for which all vertices belong to the outer face of the drawing.

In the mathematical field of graph theory, the **Heawood graph** is an undirected graph with 14 vertices and 21 edges, named after Percy John Heawood.

In the mathematical field of graph theory, the **Desargues graph** is a distance-transitive cubic graph with 20 vertices and 30 edges. It is named after Girard Desargues, arises from several different combinatorial constructions, has a high level of symmetry, is the only known non-planar cubic partial cube, and has been applied in chemical databases.

In the mathematical discipline of graph theory, a **wheel graph** is a graph formed by connecting a single universal vertex to all vertices of a cycle. A wheel graph with *n* vertices can also be defined as the 1-skeleton of an (*n*-1)-gonal pyramid. Some authors write *W*_{n} to denote a wheel graph with *n* vertices ; other authors instead use *W*_{n} to denote a wheel graph with *n*+1 vertices, which is formed by connecting a single vertex to all vertices of a cycle of length *n*. In the rest of this article we use the former notation.

In the mathematical field of graph theory, a **quartic graph** is a graph where all vertices have degree 4. In other words, a quartic graph is a 4-regular graph.

In graph theory, an area of mathematics, a **claw-free graph** is a graph that does not have a claw as an induced subgraph.

In the mathematical field of graph theory, the **Wagner graph** is a 3-regular graph with 8 vertices and 12 edges. It is the 8-vertex Möbius ladder graph.

In the mathematical field of graph theory, the **ladder graph** *L*_{n} is a planar undirected graph with *2n* vertices and *3n-2* edges.

In graph-theoretic mathematics, a **cycle double cover** is a collection of cycles in an undirected graph that together include each edge of the graph exactly twice. For instance, for any polyhedral graph, the faces of a convex polyhedron that represents the graph provide a double cover of the graph: each edge belongs to exactly two faces.

In graph theory, the **generalized Petersen graphs** are a family of cubic graphs formed by connecting the vertices of a regular polygon to the corresponding vertices of a star polygon. They include the Petersen graph and generalize one of the ways of constructing the Petersen graph. The generalized Petersen graph family was introduced in 1950 by H. S. M. Coxeter and was given its name in 1969 by Mark Watkins.

In the mathematical field of graph theory, the **Nauru graph** is a symmetric bipartite cubic graph with 24 vertices and 36 edges. It was named by David Eppstein after the twelve-pointed star in the flag of Nauru.

In the mathematical field of graph theory, the **double-star snark** is a snark with 30 vertices and 45 edges.

In geometric graph theory, a branch of mathematics, a **polyhedral graph** is the undirected graph formed from the vertices and edges of a convex polyhedron. Alternatively, in purely graph-theoretic terms, the polyhedral graphs are the 3-vertex-connected planar graphs.

In the mathematical discipline of graph theory, **Petersen's theorem**, named after Julius Petersen, is one of the earliest results in graph theory and can be stated as follows:

Petersen's Theorem.Every cubic, bridgeless graph contains a perfect matching.