TOPICS
Search

Poussin Graph


PoussinGraph

The Poussin graph is the 15-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, Heawood Four-Color Graph, Kempe Chain, Kittell 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. "Poussin Graph." From MathWorld--A Wolfram Web Resource. https://mathworld.wolfram.com/PoussinGraph.html

Subject classifications