Kittell Graph

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.

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.