TOPICS
Search

Heawood Four-Color Graph


HeawoodFour-ColorGraph

The Heawood four-color graph is the 25-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.


See also

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

Explore with Wolfram|Alpha

References

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.

Cite this as:

Weisstein, Eric W. "Heawood Four-Color Graph." From MathWorld--A Wolfram Web Resource. https://mathworld.wolfram.com/HeawoodFour-ColorGraph.html

Subject classifications