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.