Mostre que em um conjunto de
pessoas há duas pessoas que conhecem exatamente o mesmo número de pessoas do conjunto.
Passo 1
Resumindo o problema: temos um grupo de
pessoas em que “conhecer” é uma relação mútua (se A conhece B então B conhece A). Para cada pessoa definimos seu grau
como o número de pessoas que ela conhece. Queremos mostrar que, nesse grupo, existem pelo menos duas pessoas com o mesmo valor de
. O conteúdo usado será o Princípio da Casa dos Pombos (pigeonhole principle) aplicado aos graus possíveis de cada vértice em um grafo simples.
Passo 2
Observamos que, em um grafo simples com
vértices, cada vértice (pessoa) pode ter grau mínimo
(não conhece ninguém) e grau máximo
(conhece todas as outras). Logo, para as
pessoas, os graus estão entre
Passo 3
Para ter todos os graus distintos, as
pessoas teriam de ocupar exatamente os
valores
. Mas vamos mostrar que isso é impossível: não podem coexistir alguém com grau
e alguém com grau
.
Passo 4
Suponha que exista uma pessoa
com grau
. Então
conhece todas as outras
pessoas, de modo que não há ninguém com grau
. Analogamente, se alguém tivesse grau
, não poderia existir alguém com grau
. Concluímos que, na prática, apenas
valores distintos de grau podem ocorrer simultaneamente.
Passo 5
Como há
pessoas (pombos) e apenas
valores possíveis de grau (câmaras), pelo Princípio da Casa dos Pombos necessariamente duas pessoas compartilham o mesmo grau.
Resposta
Mostramos que não há como atribuir distintos todos os
valores de grau a
pessoas, sobrando um valor de grau para ser repetido. Portanto, existem sempre duas pessoas com o mesmo número de conhecidos.