Alfred Errera published it in 1921 as a counterexample to Kempe's erroneous proof of the four color theorem;[1][2] it was named after Errera by Hutchinson & Wagon (1998).

Kempe's proof can be translated into an algorithm to color planar graphs, which is also erroneous.

[3] However, until the work of Errera, these counterexamples did not show that the whole coloring algorithm fails.

Rather, they assumed that all but one vertex of the graph had already been colored, and showed that Kempe's method (which purportedly would modify the coloring to extend it to the whole graphs) failed in those precolored instances.

The Errera graph, on the other hand, provides a counterexample to Kempe's entire method.

Therefore, on this graph, it is impossible to avoid the problematic cases of Kempe's method by choosing lower-degree vertices.

The figure shows an example of how Kempe's proof can fail for this graph.

Kempe's erroneous proof follows the idea of extending partial colorings such as this one by recoloring Kempe chains, connected subgraphs that have only two colors.

In the case shown, the vertex to be colored next is the one corresponding to the outer region of the map.

But because the blue-yellow and blue-green chains cross each other rather than staying separated, there is a region in the middle of the figure where the red-yellow and red-green chains can meet.

When these two chains meet in the middle, the simultaneous swap causes adjacent yellow and green vertices in this middle area (such as the vertices represented by the upper yellow and green regions in the figure) to both become red, producing an invalid coloring.

Chemical graph theory concerns the graph-theoretic structure of molecules and other clusters of atoms.

This shape also plays a central role in the construction of higher-dimensional fullerenes.