TOPICS
Search

Kittell Graph

DOWNLOAD Mathematica NotebookDownload Wolfram Notebook
KittellGraph

The Kittell graph is a planar graph on 23 nodes and 63 edges that tangles the Kempe chains in Kempe's coloring algorithm and thus provides an example of how Kempe's (1879) supposed proof of the four-color theorem fails.

The Kittell graph is implemented in the Wolfram Language as GraphData["KittellGraph"].

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, Kempe's Coloring Algorithm, Soifer Graph, Wagon USA Map Graph

Explore with Wolfram|Alpha

References

House of Graphs. "Kittell Graph." https://houseofgraphs.org/graphs/1194.Kempe, A. B. "On the Geographical Problem of the Four Colours." Amer. J. Math. 2, 193-200, 1879. https://doi.org/10.2307/2369235.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.

Referenced on Wolfram|Alpha

Kittell Graph

Cite this as:

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

Subject classifications