Grafo de Petersen

En el campo matemático de la teoría de grafos, el grafo de Petersen es un grafo no dirigido con 10 vértices y 15 aristas . Es un grafo pequeño que sirve como ejemplo y contraejemplo para muchos problemas en la teoría de grafos. El grafo de Petersen lleva el nombre de Julius Petersen, quien en 1898 lo construyó para ser el grafo cúbico sin puentes más pequeño que no se puede 3-colorear.​ Aunque comúnmente se le da crédito a Petersen, en realidad apareció por primera vez 12 años antes, en un artículo de A. B. Kempe. Kempe observó que sus vértices pueden representar las diez líneas de la configuración de Desargues, y sus bordes representan pares de líneas que no se encuentran en uno de los diez puntos de la configuración. Donald Knuth afirma que el grafo de Petersen es "una configuración notable que sirve como contraejemplo a muchas predicciones optimistas sobre qué podría ser cierto en un grafo en general."​