Dans un groupe de $n$ personnes, on définit une "amitié" comme une relation symétrique. Montrer que :
Dans tout groupe de 6 personnes, il existe soit 3 personnes qui se connaissent toutes, soit 3 personnes qui ne se connaissent pas mutuellement.
Le résultat est faux pour 5 personnes : construire un exemple.
Solution
Cas de 6 personnes (Ramsey $R(3,3) = 6$) :
Soit $A$ une personne parmi 6. Elle a 5 relations. Par le principe des tiroirs, elle connaît $\ge 3$ personnes ou elle ne connaît pas $\ge 3$ personnes. Cas 1 : $A$ connaît $B, C, D$. Si un des pairs $BC, BD, CD$ se connaît, on forme un trio d'amis avec $A$. Sinon, $B, C, D$ ne se connaissent pas mutuellement. Cas 2 : Symétrique en "ne pas connaître".
Dans tous les cas, on trouve 3 personnes du même type.
Contre-exemple pour 5 personnes :
Placer 5 personnes aux sommets d'un pentagone régulier. Chaque personne "connaît" ses deux voisins immédiats et "ne connaît pas" les deux autres.
Ce graphe est le cycle $C_5$, qui ne contient ni clique de taille 3 ni ensemble indépendant de taille 3. ✓