Seja
Gn o grafo parcial de
Kn, com ordem
n > 3, que se obtem deste último removendo
três arestas ligando três vértices (i.e. um triângulo).
O número cromático dum grafo
G
será aqui denotado por ¢(G).
Mostre que ¢(Gn)=n - 2.
Justifique porque são planares os grafos
G4 e
G5.
Mostre que Gn
não é planar se n > 5.
Represente G5
como um grafo planar topológico e obtenha o
dual desse grafo planar topológico.