In graph theory, the Poussin graph is a

planar graph In graph theory, a planar graph is a graph (discrete mathematics), graph that can be graph embedding, embedded in the plane (geometry), plane, i.e., it can be drawn on the plane in such a way that its edges intersect only at their endpoints. ...

with 15 vertices and 39 edges. It is named after

Charles Jean de la Vallée-Poussin Charles is a masculine given name predominantly found in English and French speaking countries. It is from the French form ''Charles'' of the Proto-Germanic name (in runic alphabet) or ''*karilaz'' (in Latin alphabet), whose meaning wa ...

History

In 1879,

Alfred Kempe Sir Alfred Bray Kempe FRS (6 July 1849 – 21 April 1922) was a mathematician best known for his work on linkages and the four colour theorem. Biography Kempe was the son of the Rector of St James's Church, Piccadilly, the Rev. John Edwar ...

published a proof of the

four color theorem In mathematics, the four color theorem, or the four color map theorem, states that no more than four colors are required to color the regions of any map so that no two adjacent regions have the same color. ''Adjacent'' means that two regions shar ...

, one of the big conjectures in

graph theory In mathematics and computer science, graph theory is the study of ''graph (discrete mathematics), graphs'', which are mathematical structures used to model pairwise relations between objects. A graph in this context is made up of ''Vertex (graph ...

. While the theorem is true, Kempe's proof is incorrect.

Percy John Heawood Percy John Heawood (8 September 1861 – 24 January 1955) was a British mathematician, who concentrated on graph colouring. Life He was the son of the Rev. John Richard Heawood of Newport, Shropshire, and his wife Emily Heath, daughter of the ...

illustrated it in 1890 with a counter-example, and de la Vallée-Poussin reached 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

mathematicians remain interested in such counterexamples. More were found later: first, the

Errera graph In the mathematics, mathematical field of graph theory, the Errera graph is a graph with 17 vertex (graph theory), vertices and 45 edge (graph theory), edges. Alfred Errera published it in 1921 as a counterexample to Alfred Kempe, Kempe's erroneous ...

in 1921, then the

Kittell graph In the mathematical field of graph theory, the Kittell graph is a planar graph with 23 vertices and 63 edges. Its unique planar embedding has 42 triangular faces. The Kittell graph is named after Irving Kittell, who used it as a counterexample t ...

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).Gethner, E. and Springer, W. M. II. « How False Is Kempe's Proof of the Four-Color Theorem? » Congr. Numer. 164, 159–175, 2003.

References

{{Reflist

External links

Eric W. Weisstein Eric Wolfgang Weisstein (born March 18, 1969) is an American scientist, mathematician, and encyclopedist who created and maintains the encyclopedias ''MathWorld'' and ''ScienceWorld''. In addition, he is the author of the '' CRC Concise Ency ...

Poussin Graph
(

MathWorld ''MathWorld'' is an online mathematics reference work, created and largely written by Eric W. Weisstein. It is sponsored by and licensed to Wolfram Research, Inc. and was partially funded by the National Science Foundation's National Science ...

) Individual graphs