TOPICS
Search

Soifer Graph


SoiferGraph

The Soifer graph, illustrated above in a number of embeddings, 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).

SoiferGraphFritschGraph

Adding a particular edge to the Soifer graph gives the Fritsch graph.

The Soifer graph is implemented in the Wolfram Language as GraphData["SoiferGraph"].


See also

Errera Graph, Four-Color Theorem, Fritsch Graph, Heawood Four-Color Graph, Kempe Chain, Kittell Graph, Poussin 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.Soifer, A. "Map Coloring in the Victorian Age: Problems and History." Math. Competitions 10, 20-31, 1997.

Cite this as:

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

Subject classifications