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, é planar também?
  2. Qual o número cromático de G2,3?
  3. Qual o índice cromático de G2,3?
  4. Qual o maior número de componentes conexas que um subgrafo de Gp,q pode ter? Porquê?
  5. Identifique, através de uma condição em p e q, o conjunto dos valores de p e q para os quais Gp,q não admite ciclos hamiltonianos. Deve justificar completamente a sua resposta. Se não conseguir resolver esta alínea mostre que G3,4 não admite ciclos hamiltonianos.