Content deleted Content added
→Fritsch graph: here |
|||
Line 50:
== Fritsch graph ==
[[File:Fritsch map.svg|thumb|left|The Fritsch graph and its dual map. For the partial 4-coloring shown, the red–green and blue–green [[Kempe chain]]s cross. It is not possible to free a color for the uncolored center region by swapping colors in a single chain, contradicting [[Alfred Kempe]]'s false proof of the four color theorem.]]
The graph of the triaugmented triangular prism has 9 vertices and 21 edges. It was used by {{harvtxt|Fritsch|Fritsch|1998}} as a small counterexample to [[Alfred Kempe]]'s false proof of the [[four color theorem]] using [[Kempe chain]]s, and its dual map was used as their book's cover illustration.{{r|ff98}} Therefore, this graph has subsequently been named the '''Fritsch graph'''.{{r|involve}} An even smaller counterexample, called the Soifer graph, is obtained by removing one edge from the Fritsch graph (the bottom edge in the illustration here).{{r|involve|soifer}}
The Fritsch graph is one of only six connected graphs in which the [[Neighbourhood (graph theory)|neighborhood]] of every vertex is a cycle of length four or five. More generally, when every vertex in a graph has a cycle of length at least four as its neighborhood, the triangles of the graph automatically link up to form a [[manifold|topological surface]] called a [[Triangulation (topology)|Whitney triangulation]]. These six graphs come from the six Whitney triangulations that, when their triangles are equilateral, have positive [[angular defect]] at every vertex. This makes them a combinatorial analogue of the positively curved smooth surfaces. They come from six of the eight deltahedra—excluding the two that have a vertex with a triangular neighborhood. As well as the Fritsch graph, the other five are the graphs of the [[regular octahedron]], [[regular icosahedron]], [[pentagonal bipyramid]], [[snub disphenoid]], and [[gyroelongated square bipyramid]].{{r|knill}}
| |||