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.
- Mostre que G3,2 é planar.
- Quantas arestas tem Gp,q?
- Qual o maior grau de vértice em Gp,q?
- Numa coloração de arestas de G6,3
qual o maior número de arestas que pode haver da mesma cor?
- Qual o índice cromático de G6,3?