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.
- Mostre que G2,3 é planar.
E G3,3, é planar também?
- Qual o número cromático de G2,3?
- Qual o índice cromático de G2,3?
- Qual o maior número de componentes conexas que um subgrafo de
Gp,q pode ter? Porquê?
- 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.