TOPICS
Search

Errera Graph


ErreraGraph

The Errera graph is the 17-node planar graph illustrated above that tangles the Kempe chains in Kempe's algorithm and thus provides an example of how Kempe's supposed proof of the four-color theorem fails.

The Fritsch graph and Soifer graph provide smaller (and in fact the smallest possible) counterexamples.

ErreraGraphEmbeddings

A number of other embeddings (many of which are vertex-vertex and/or edge-vertex degenerate) are illustrated above.

ErreraGraphEmbeddings3D

The Errera graph has no planar unit-distance embedding (since it contains the 9-node triangular cupola unit-distance forbidden graph), but a beautiful three-dimensional unit-distance embedding can be obtained from two oppositely-oriented copies of a gyroelongated pentagonal pyramid, i.e., a truncated regular icosahedron with one vertex and adjoining faces removed, adjoined at their pentagonal faces (E. Weisstein, Mar. 8, 2022). This is related to its being the dual graph of the (30,1)-fullerene, which is one of the three fullerenes on 30 vertices.


See also

Four-Color Theorem, Fritsch Graph, Heawood Four-Color Graph, Kempe Chain, Kittell Graph, Poussin Graph, Soifer Graph

Explore with Wolfram|Alpha

References

Errera, A. Du colorage de cartes et de quelques questions d'analysis situs. Ph.D. thesis. Paris: Gauthier-Villars, 1921.Gethner, E. and Springer, W. M. II. "How False Is Kempe's Proof of the Four-Color Theorem?" Congr. Numer. 164, 159-175, 2003.Kempe, A. B. "On the Geographical Problem of Four-Colors." Amer. J. Math. 2, 193-200, 1879.Tilley, J. A. "Using Kempe Exchanges to Disentangle Kempe Chains." Math. Intell. 40, 50-54, 2018.Wagon, S. Mathematica in Action, 2nd ed. New York: Springer-Verlag, pp. 522-524, 1999.

Cite this as:

Weisstein, Eric W. "Errera Graph." From MathWorld--A Wolfram Web Resource. https://mathworld.wolfram.com/ErreraGraph.html

Subject classifications