Seja G um grafo simples. Designaremos por k(G) o maior inteiro n tal que o grafo completo Kn é isomorfo a um subgrafo de G.
O número cromático do grafo G será aqui denotado por ¢(G).

Seja Gn o grafo parcial de Kn que se obtem removendo três arestas unindo três vértices (i.e. um triângulo).
Supondo que n > 3, qual das seguintes alternativas está correcta?

k(Gn)=n - 1 e ¢(Gn)<=n - 1
k(Gn)=n - 3 e ¢(Gn)>=n - 3
k(Gn)=n - 1 e ¢(Gn)>=n - 1
k(Gn)=n - 2 e ¢(Gn)>=n - 2