Named after Alfred Errera Edges 45 Diameter 4 | Vertices 17 Radius 3 Girth 3 | |
 | ||
In the mathematical field of graph theory, the Errera graph is a graph with 17 vertices and 45 edges discovered by Alfred Errera. Published in 1921, it provides an example of how Kempe's proof of the four color theorem cannot work.
Later, the Fritsch graph and Soifer graph provide two smaller counterexamples.
The Errera graph is planar and has chromatic number 4, chromatic index 6, radius 3, diameter 4 and girth 3. All its vertices are of degree 5 or 6 and it is a 5-vertex-connected graph and a 5-edge-connected graph.
Algebraic properties
The Errera graph is not a vertex-transitive graph and its full automorphism group is isomorphic to the dihedral group of order 20, the group of symmetries of a decagon, including both rotations and reflections.
The characteristic polynomial of the Errera graph is