A resposta correcta é a 4ª. 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 fosse k(Gn)>=n - 1 existiria um subgrafo H de Gn que seria um grafo completo de ordem n - 1. Esse subgrafo teria de conter pelo menos dois dos vértices v1, v2 e v3. Logo teria de conter pelo menos uma das três arestas, ligando estes vértices, e não poderia ser um subgrafo de Gn. Deste absurdo concluímos que k(Gn)=n - 2.
Por outro lado é obvio que ¢(Gn)>=k(Gn), ou seja ¢(Gn)>=n - 2.