Seja Gp,q o grafo que se obtem do grafo completo Kp juntando-lhe q novos vértices e todas as arestas que os ligam aos vértices de Kp. Na figura seguinte vem representado o grafo G3,2.
Se não conseguir resolver as alíneas $4.$ e $5.$ para o grafo G6,3 tente pelo menos resolvê-las para o grafo G3,2.
  1. Mostre que G3,2 é planar.
  2. Quantas arestas tem Gp,q?
  3. Qual o maior grau de vértice em Gp,q?
  4. Numa coloração de arestas de G6,3 qual o maior número de arestas que pode haver da mesma cor?
  5. Qual o índice cromático de G6,3?

Respostas

  1. O grafo planar seguinte é isomorfo a G3,2.

  2. Gp,q tem q   p + p  (p-1)/2 arestas.
  3. O maior grau de vértice em Gp,q é q + p - 1.
  4. Numa coloração de arestas de G6,3 o maior número de arestas que pode haver da mesma cor é 4. Havendo 5 arestas da mesma cor, isto implicaria que o grafo tivesse pelo menos 10 vértices. Como o grafo G6,3 tem ordem 9 isto não é possível.
  5. O índice cromático de G6,3 é 9. Pelo Teorema de Vizing o índice cromático é igual a 8 ou 9. Não existe nenhuma coloração de arestas de G6,3 em 8 cores porque senão o número de arestas seria no máximo $32=8 × 4 . Mas G6,3 tem 33 arestas.