Graphe de Petersen

Le graphe de Petersen est, en théorie des graphes, un graphe particulier possédant 10 sommets et 15 arêtes. Il s'agit d'un petit graphe qui sert d'exemple et de contre-exemple pour plusieurs problèmes de la théorie des graphes. Il porte le nom du mathématicien Julius Petersen, qui l'introduisit en 1898 en tant que plus petit graphe cubique sans isthme dont les arêtes ne peuvent être colorées avec trois couleurs. Il a cependant été mentionné par Alfred Kempe pour la première fois 12 ans auparavant, en 1886. Donald Knuth explique dans The Art of Computer Programming que le graphe de Petersen est « une configuration remarquable qui sert de contre-exemple à de nombreuses prédictions optimistes sur ce qui devrait être vrai pour tous les graphes ».