Mostre que em um grupo de cinco pessoas (em que duas pessoas são amigas ou inimigas) não há necessariamente três amigos mútuos ou três inimigos mútuos.
Passo 1
O enunciado fala de um grupo de cinco pessoas em que toda dupla é ou amiga ou inimiga, e pede para mostrar que não é forçado existir três amigos mútuos nem três inimigos mútuos. Esse é um problema típico de Teoria de Ramsey: sabemos que
, ou seja, com
vértices ainda podemos colorir as arestas de um grafo de forma a evitar qualquer triângulo monocromático. Vamos então construir um contraexemplo explícito.
Passo 2
Rotule as cinco pessoas por
. Definimos que são amigas exatamente as duplas
e todas as outras duplas são inimigas.
Passo 3
O grafo de amizade é então um ciclo de comprimento
, chamado
. É sabido que
não tem triângulo, pois em qualquer ciclo de comprimento maior que
não há três vértices mutuamente ligados. Logo não existem três amigos mútuos.
Passo 4
O grafo de inimizades é o complemento de
. Mas o complemento de um ciclo de comprimento
é novamente um ciclo de comprimento
, também sem triângulo. Portanto não existem três inimigos mútuos.
Resposta
Um contraexemplo é tomar os “amigos” como as arestas de um ciclo com
vértices. Nem o grafo de amizades nem o de inimizades contém triângulo, logo não há necessariamente três amigos mútuos nem três inimigos mútuos em um grupo de cinco pessoas.