Grafo de Gray

No campo da matemática da teoria dos grafos o grafo de Gray é um grafo não direcionado bipartido, com 54 vértices e 81 arestas. É um grafo cúbico: todo vértice toca exatamente três arestas. Foi descoberto por Marion C. Gray, em 1932, (de forma inédita), em seguida, descoberto independentemente por Bouwer 1968, em resposta a uma pergunta feita por em 1967. O grafo de Gray é interessante como o primeiro exemplo conhecido de um grafo cúbico tendo a propriedade algébrica de ser aresta-transitivo, mas não sendo vértice-transitivo (ver abaixo). O grafo de Gray tem um número cromático 2, índice cromático 3, raio 6 e diâmetro 6. Ele é também um grafo 3- e 3-aresta-conectado não-planar.