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?
- Mostre que G2,3 não admite
ciclos hamiltonianos. E G3,3?
- Qual o maior número de componentes conexas que um subgrafo de
Gp,q pode ter?
- Qual o número cromático de G2,3?
- Qual o índice cromático de G2,3?