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?
Respostas
- O grafo planar seguinte é isomorfo a G3,2.
- Gp,q
tem
q p + p (p-1)/2
arestas.
- O maior grau de vértice em Gp,q é
q + p - 1.
- Numa coloração de arestas de G6,3
o maior número de arestas que pode haver da mesma cor é
4. Havendo 5 arestas da mesma cor,
isto implicaria que o grafo tivesse pelo menos 10 vértices.
Como o grafo G6,3 tem ordem
9 isto não é possível.
- O índice cromático de G6,3
é 9. Pelo Teorema de Vizing o índice cromático
é igual a 8 ou 9.
Não existe nenhuma coloração de arestas de
G6,3 em 8
cores porque senão o número de arestas seria no máximo
$32=8 × 4 .
Mas
G6,3 tem
33 arestas.