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).
Adding a particular edge to the Soifer graph gives the Fritsch graph.
The Soifer graph is implemented in the Wolfram Language as GraphData["SoiferGraph"].
