Kempe Chain

Let G be a planar graph whose vertices have been properly colored and suppose v in V(G) is colored C_1. Define the C_1C_2-Kempe chain containing v to be the maximal connected component of G that

1. Contains v, and

2. Contains only vertices that are colored with elements from (C_1,C_2)

(Gethner and Springer 2003).


A number of small graphs (with n the vertex count) that tangle the chains in Kempe's algorithm and so provide examples of how Kempe's supposed proof of the four-color theorem fails are illustrated above and summarized in the following table.


Interestingly, a number of these examples (though not the Soifer graph, which contains a 4-cycle) correspond to the skeletons of (possibly degenerate) deltahedra (E. Weisstein, Mar. 7, 2022). In particular, the Fritsch graph is the skeleton of the triaugmented triangular prism and the Errera graph is the skeleton of two pentagon-adjoined gyroelongated pentagonal pyramids.

See also

Errera Graph, Four-Color Theorem, Fritsch Graph, Heawood Four-Color Graph, Kittell Graph, Poussin Graph, Soifer Graph

Explore with Wolfram|Alpha


Gethner, E. and Springer, W. M. II. "How False Is Kempe's Proof of the Four-Color Theorem?" Congr. Numer. 164, 159-175, 2003.Hutchinson, J. P. and Wagon, S. "Kempe Revisited." Amer. Math. Monthly 105, 170-174, 1998.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. 535-536, 1999.

Referenced on Wolfram|Alpha

Kempe Chain

Cite this as:

Weisstein, Eric W. "Kempe Chain." From MathWorld--A Wolfram Web Resource.

Subject classifications