Errera graph
| Errera graph | |
|---|---|
|
The Errera graph | |
| Named after | Alfred Errera |
| Vertices | 17 |
| Edges | 45 |
| Radius | 3 |
| Diameter | 4 |
| Girth | 3 |
| Automorphisms | 20 (D10) |
| Chromatic number | 4 |
| Chromatic index | 6 |
| Properties |
Planar Hamiltonian[1] |
In the mathematical field of graph theory, the Errera graph is a graph with 17 vertices and 45 edges discovered by Alfred Errera.[2] Published in 1921, it provides an example of how Kempe's proof of the four color theorem cannot work.[3][4]
Later, the Fritsch graph and Soifer graph provide two smaller counterexamples.[5]
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 .
Gallery
-
The chromatic number of the Errera graph is 4.
-
The chromatic index of the Errera graph is 6.
-
The Errera graph is planar.
References
- ↑ 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.