Grafo de Petersen

No campo da matemática da teoria dos grafos o grafo de Petersen é um grafo não-orientado com 10 vértices e 15 arestas. É um pequeno grafo que serve como um exemplo útil e contra-exemplo para muitos problemas em teoria dos grafos. O grafo de Petersen é nomeado em honra a Julius Petersen, que em 1898 construiu o menor grafo cúbico sem ponte cujas arestas não podem ser coloridas com somente três cores. Embora o grafo seja geralmente creditado a Petersen, ele tinha, de facto, aparecido pela primeira vez 12 anos antes, em 1886. Donald Knuth afirma que o grafo de Petersen é "uma configuração notável que serve como um contra-exemplo para muitas previsões otimistas sobre o que poderia ser verdade para os grafos em geral."