Soifer Graph

The Soifer graph is a planar graph on 9 nodes 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. As proved by Gethner and Springer, the Soifer graph is the smallest such counterexample (and is smaller than the Kittell graph and Errera graph).

It is implemented in the Wolfram Language as GraphData["SoiferGraph"].

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.

Soifer, A. "Map Coloring in the Victorian Age: Problems and History." Math. Competitions 10, 20-31, 1997.