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 R(3,3)=6, ou seja, com 5 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 1,2,3,4,5. Definimos que são amigas exatamente as duplas
\{1,2\},\\ \{2,3\},\\ \{3,4\},\\ \{4,5\},\\ \{5,1\},
e todas as outras duplas são inimigas.

Passo 3

O grafo de amizade é então um ciclo de comprimento 5, chamado C_5. É sabido que C_5 não tem triângulo, pois em qualquer ciclo de comprimento maior que 3 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 C_5. Mas o complemento de um ciclo de comprimento 5 é novamente um ciclo de comprimento 5, 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 5 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.

Exercícios relacionados