Dans le pire des cas, chaque personne connaît exactement

autres personnes.

et

sont deux personnes distinctes. Si l'on admet qu'elles ne se connaissent pas, alors

et

appartiennent à deux groupes de personnes différents.
Si quatre personnes ne peuvent pas être disposées en cercle de façon à ce que chaque personne connaisse ses voisins, il n'y aurait que deux groupes.
Soit

le groupe de

composé donc de

personnes. Parmis

toutes les personnes se connaissent entre elles.

est le groupe de

composé aussi d'au moins

personnes.

Il y a deux personnes qui appartiennent aux deux groupes, il est donc impossible de séparer les

personnes en deux groupes de telle sorte qu'aucune personne d'un groupe connaisse une personne de l'autre groupe.
Il y aura alors au minimum deux personnes qui appartiennent aux deux groupes.
Soit

et

ces deux personnes.
Alors,

connaît

qui connaît

qui connaît

qui connaît

.