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.
O grafo de Petersen é o complementar do grafo linha de K 5 {\displaystyle K_{5}} . É também o grafo Kneser K G 5 , 2 {\displaystyle KG_{5,2}} ; isso significa que ele tem um vértice para cada subconjunto de dois elementos de um conjunto de 5 elementos, e dois vértices são conectados por uma aresta se e somente se os correspondentes subconjuntos de dois elementos são disjuntos entre si. Como um grafo de Kneser da forma K G 2 n − 1 , n − 1 {\displaystyle KG_{2n-1,n-1}} é um exemplo de um grafo ímpar. Geometricamente, o grafo de Petersen é o grafo formado pelos vértices e arestas do hemi-dodecaedro, ou seja, um dodecaedro com os pontos opostos, linhas e faces identificadas em conjunto.
O grafo de Petersen é não-planar. Qualquer grafo não planar tem como menores tanto o grafo completo K 5 {\displaystyle K_{5}} , quanto o grafo bipartido completo K 3 , 3 {\displaystyle K_{3,3}} , mas o grafo de Petersen tem ambos os menores. O K 5 {\displaystyle K_{5}} menor pode ser formado restringindo-se as arestas de um acoplamento perfeito, por exemplo as cinco arestas curtas na primeira figura. O menor K 3 , 3 {\displaystyle K_{3,3}} pode ser formado se deletando um vértice (por exemplo, o vértice central do desenho do 3-simétrico) e contratando uma aresta incidente para cada vizinho do vértice que foi excluído. O mais comum e simétrico desenho do plano do grafo de Petersen, como um pentagrama dentro de um pentágono, tem cinco cruzamentos. No entanto, este não é o melhor desenho que minimiza os cruzamentos; existe um outro desenho (mostrado na figura), com apenas dois cruzamentos. Assim, o grafo de Petersen tem número de cruzamento 2. Em um toro o grafo de Petersen pode ser desenhado sem cruzamentos de arestas; tem, portanto, gênero orientável 1.
O grafo de Petersen é fortemente regular (com assinatura srg(10,3,0,1)). É também simétrico, o que significa que é aresta-transitivo e vértice-transitivo. Mais fortemente, é de 3-arcos-transitivo: cada caminho de três arestas dirigidas no grafo de Petersen pode ser transformado em qualquer outro tipo de percurso por uma simetria do grafo.
