TOPICS
Search

Kittell Graph


KittellGraph

The Kittell graph is a planar graph on 23 nodes and 63 edges 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.

It is also an identity graph.

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


See also

Errera Graph, Four-Color Theorem, Kempe Chain, Soifer Graph

Explore with Wolfram|Alpha

References

Kempe, A. B. "On the Geographical Problem of Four-Colors." Amer. J. Math. 2, 193-200, 1879.Kittell, I. "A Group of Operations on a Partially Colored Map." Bull. Amer. Math. Soc. 41, 407-413, 1935.Wagon, S. Mathematica in Action, 2nd ed. New York: Springer-Verlag, pp. 533-534, 1999.

Cite this as:

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

Subject classifications