# Poussin graph

> Mediated Wiki article. Canonical URL: https://mediated.wiki/source/Poussin_graph
> Markdown URL: https://mediated.wiki/source/Poussin_graph.md
> Source: https://en.wikipedia.org/wiki/Poussin_graph
> Source revision: 1236309374
> License: Creative Commons Attribution-ShareAlike 4.0 International (https://creativecommons.org/licenses/by-sa/4.0/)

In graph theory, the **Poussin graph** is a [planar graph](/source/Planar_graph) with 15 vertices and 39 edges. It is named after [Charles Jean de la Vallée-Poussin](/source/Charles_Jean_de_la_Vall%C3%A9e-Poussin).

## History

In 1879, [Alfred Kempe](/source/Alfred_Kempe) published a proof of the [four color theorem](/source/Four_color_theorem), one of the big conjectures in [graph theory](/source/Graph_theory).[1] While the theorem is true, Kempe's proof is incorrect. [Percy John Heawood](/source/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](/source/Kempe_chain), and as those chains prove useful in [graph theory](/source/Graph_theory) mathematicians remain interested in such counterexamples. More were found later: first, the [Errera graph](/source/Errera_graph) in 1921,[4][5] then the [Kittell graph](/source/Kittell_graph) in 1935, with 23 vertices,[6] and finally two minimal counter-examples (the [Soifer graph](/source/Soifer_graph) in 1997 and the [Fritsch graph](/source/Fritsch_graph) in 1998, both of order 9).[7][8][9]

## References

1. Kempe, A. B. "On the Geographical Problem of Four-Colors." Amer. J. Math. 2, 193–200, 1879.

1. P. J. Heawood, "Map colour theorem", Quart. J. Pure Appl. Math. 24 (1890), 332–338.

1. R. A. Wilson, Graphs, colourings and the four-colour theorem, Oxford University Press, Oxford, 2002. MR [1888337](https://mathscinet.ams.org/mathscinet-getitem?mr=1888337) Zbl [1007.05002](https://zbmath.org/?q=an:1007.05002).

1. Errera, A. "Du coloriage des cartes et de quelques questions d'analysis situs." Ph.D. thesis. 1921.

1. Peter Heinig. [Proof that the Errera Graph is a narrow Kempe-Impasse](http://www-m9.ma.tum.de/foswiki/pub/Allgemeines/PeterHeinig/erreraGraphIsNarrowProof.pdf). 2007.

1. Kittell, I. "A Group of Operations on a Partially Colored Map." Bull. Amer. Math. Soc. 41, 407–413, 1935.

1. A. Soifer, “Map coloring in the victorian age: problems and history”, Mathematics Competitions 10 (1997), 20–31.

1. R. Fritsch and G. Fritsch, The Four-Color Theorem, Springer, New York, 1998. MR [1633950](https://mathscinet.ams.org/mathscinet-getitem?mr=1633950).

1. Gethner, E. and Springer, W. M. II. « How False Is Kempe's Proof of the Four-Color Theorem? » Congr. Numer. 164, 159–175, 2003.

## External links

- [Eric W. Weisstein](/source/Eric_W._Weisstein), [Poussin Graph](http://mathworld.wolfram.com/PoussinGraph.html) ([MathWorld](/source/MathWorld))

---
Adapted from the Wikipedia article [Poussin graph](https://en.wikipedia.org/wiki/Poussin_graph) by Wikipedia contributors ([contributor history](https://en.wikipedia.org/wiki/Poussin_graph?action=history)). Available under [Creative Commons Attribution-ShareAlike 4.0 International](https://creativecommons.org/licenses/by-sa/4.0/). Changes may have been made.