Bonjour,

Voici un exercice de graphes que je n'arrive pas à résoudre :

Supposons G un graphe et n(G) le nombre de stabilité de G.
Montrer que si |S(G)|>=6 alors n(G)>=3 ou n(Gc)>=3, où |S(G)|est le nombre de sommets et Gc le graphe complémentaire de G.

On m'a donné l'idée de démonstration suivante :
On part d'un graphe G d'ordre 6, 7, 8,... tel que n(G)<=2 et on montre qu'alors n(Gc)>=3, dire que n(G)<=2 signifie que la taille d'une plus grande partie stable de G est 2 (ou 1): il y a deux sommets non reliés.
Et dès que l'on prend 3 sommets il y a une arête entre ces 3 sommets.

Est-ce que quelqu'un pourrait m'aider à comprendre l'idée de démonstration svp car je ne l'ai pas vraiment comprise ou si vous auriez une nouvelle idée de démonstration elle sera la bienvenue!

Merci.