Vertices 15 Radius 3 Girth 3 | Edges 39 Diameter 3 Automorphisms 2 (Z/2Z) | |
 | ||
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 . While the theorem is true, Kempe's proof is incorrect.. Heawood illustrates it in 1890 with a counter-example, and Vallée Poussin reaches the same conclusion in 1896 with the Poussin graph .
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 · , then the Kittell graph in 1935, with 23 vertices , and finally two minimal counter-examples (the Soifer graph in 1997 and the Fritsch graph in 1998, both of order 9) · · .