- Sejam v1,
v2 e v3
os vértices de Gn que são extremidades
das três arestas removidas. Considere o subgrafo
H gerado por todos os vértices de
Kn excepto
v1 e
v2, num
total de n - 2 vértices. H
é um grafo completo de ordem n - 2
que não contem nenhuma das três arestas: {v1, v2}
, {v1, v3}
e {v2, v3}.
Logo k(Gn)>=n - 2.
Se colorirmos os vértices v1,
v2 e v3
da mesma cor e cada um dos restantes com uma cor diferente
obtemos uma coloração de vértices com n - 2
cores. Logo
¢(Gn)=n - 2.
- Representação planar de
G4.
Representação planar de
G5.
- O grafo G6,
representado na figura seguinte,
não é planar porque contem o grafo bipartido
completo K3,3,
representado abaixo,
como subgrafo parcial. (c.f. Teorema de Kuratowski)
Para n > 6 o grafo
Gn contem um subgrafo
completo de ordem maior ou igual a 5
e portanto também não é planar. (c.f. Teorema de Kuratowski)
- Dual da representação planar anterior do grafo
G5.