Poussin graph
Poussin graph | |
---|---|
![]() | |
Vertices | 15 |
Edges | 39 |
Radius | 3 |
Diameter | 3 |
Girth | 3 |
Automorphisms | 2 (Z/2Z) |
Chromatic number | 4 |
Chromatic index | 6 |
Properties | Hamiltonian Planar |
Table of graphs and parameters |
![](http://up.wiki.x.io/wikipedia/commons/thumb/3/3b/Poussin_graph_tangled_Kempe_chains.svg/400px-Poussin_graph_tangled_Kempe_chains.svg.png)
In graph theory, the Poussin graph is a planar graph with 15 vertices and 39 edges. It is named after Charles Jean de la Vallée-Poussin.
History
[edit]In 1879, Alfred Kempe published a proof of the four color theorem, one of the big conjectures in graph theory.[1] While the theorem is true, Kempe's proof is incorrect. Percy John Heawood illustrated it in 1890[2] with a counter-example, and de la Vallée-Poussin reached the same conclusion in 1896 with the Poussin graph.[3]
Kempe's (incorrect) proof is based on alternating chains, and as those chains prove useful in graph theory mathematicians remain interested in such counterexamples. More were found later: first, the Errera graph in 1921,[4][5] then the Kittell graph in 1935, with 23 vertices,[6] and finally two minimal counter-examples (the Soifer graph in 1997 and the Fritsch graph in 1998, both of order 9).[7][8][9]
References
[edit]- ^ Kempe, A. B. "On the Geographical Problem of Four-Colors." Amer. J. Math. 2, 193–200, 1879.
- ^ P. J. Heawood, "Map colour theorem", Quart. J. Pure Appl. Math. 24 (1890), 332–338.
- ^ R. A. Wilson, Graphs, colourings and the four-colour theorem, Oxford University Press, Oxford, 2002. MR1888337 Zbl 1007.05002.
- ^ 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.
- ^ Kittell, I. "A Group of Operations on a Partially Colored Map." Bull. Amer. Math. Soc. 41, 407–413, 1935.
- ^ A. Soifer, “Map coloring in the victorian age: problems and history”, Mathematics Competitions 10 (1997), 20–31.
- ^ R. Fritsch and G. Fritsch, The Four-Color Theorem, Springer, New York, 1998. MR1633950.
- ^ Gethner, E. and Springer, W. M. II. « How False Is Kempe's Proof of the Four-Color Theorem? » Congr. Numer. 164, 159–175, 2003.