TOPICS
Search

Soifer Graph

DOWNLOAD Mathematica NotebookDownload Wolfram Notebook
SoiferGraph

The Soifer graph, illustrated above in a number of drawings, is a planar graph on 9 nodes that tangles the Kempe chains in Kempe's coloring algorithm and thus provides an example of how Kempe's (1879) supposed proof of the four-color theorem fails. As proved by Gethner and Springer (2003), 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 Map, Kempe Chain, Kempe's Coloring Algorithm, Kempe-Kittell Coloring Algorithm, Kittell Graph, Poussin Graph, Wagon USA Map 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.House of Graphs. "Soifer Graph." https://houseofgraphs.org/graphs/1327.Kempe, A. B. "On the Geographical Problem of the Four Colours." Amer. J. Math. 2, 193-200, 1879. https://doi.org/10.2307/2369235.Soifer, A. "Map Coloring in the Victorian Age: Problems and History." Math. Competitions 10, 20-31, 1997.Soifer, A. The New Mathematical Coloring Book: Mathematics of Coloring and the Colorful Life of Its Creators, 2nd ed. New York: Springer, pp. 223-225, 2024.

Referenced on Wolfram|Alpha

Soifer Graph

Cite this as:

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

Subject classifications