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?