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 | |
In graph theory, the Poussin graph is a particular graph with 15 vertices and 39 edges.
History
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.. Heawood illustrates it in 1890 [2] with a counter-example, and Vallée Poussin reaches 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 counter-examples. 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
- ^ 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. MR 2003c:05095 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. MR 99i:05079.
- ^ Gethner, E. and Springer, W. M. II. « How False Is Kempe's Proof of the Four-Color Theorem? » Congr. Numer. 164, 159–175, 2003.