Errera graph

Errera graph
The Errera graph
Named after	Alfred Errera
Vertices	17
Edges	45
Radius	3
Diameter	4
Girth	3
Automorphisms	20 (D₁₀)
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 $-(x^2-2 x-5) (x^2+x-1)^2 (x^3-4 x^2-9 x+10) (x^4+2 x^3-7 x^2-18 x-9)^2$ .

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.

This article is issued from Wikipedia - version of the 5/11/2016. The text is available under the Creative Commons Attribution/Share Alike but additional terms may apply for the media files.