graphe de Petersen

COMBINATOIRE

En théorie des graphes, le graphe de Petersen a été défini en 1898 comme plus petit graphe cubique sans isthme dont les arêtes ne peuvent être coloriées avec trois couleurs. C’est un graphe de Kneser : le KG5,2.

C’est un graphe non-planaire. Géométriquement, il est formé par les sommets et les arêtes de l’hémi-dodécaèdre.
L’informaticien Donald Knuth le considère comme « une configuration remarquable qui sert de contre-exemple à de nombreuses prédictions optimistes sur ce qui devrait être vrai pour tous les graphes ».