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 G2,3.

  1. Mostre que G2,3 é planar. E G3,3?
  2. Mostre que G2,3 não admite ciclos hamiltonianos. E G3,3?
  3. Qual o maior número de componentes conexas que um subgrafo de Gp,q pode ter?
  4. Qual o número cromático de G2,3?
  5. Qual o índice cromático de G2,3?