The Errera graph
|Named after||Alfred Errera|
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.
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 .
The chromatic number of the Errera graph is 4.
The chromatic index of the Errera graph is 6.
The Errera graph is planar.
- Weisstein, Eric W., "Hamiltonian Graph", MathWorld.
- Weisstein, Eric W., "Errera graph", MathWorld.
- Errera, A. "Du coloriage des cartes et de quelques questions d'analysis situs." Ph.D. thesis. 1921.
- Peter Heinig. Proof that the Errera Graph is a narrow Kempe-Impasse. 2007.
- Gethner, E. and Springer, W. M. II. "How False Is Kempe's Proof of the Four-Color Theorem?" Congr. Numer. 164, 159-175, 2003.