Uma rede de computadores é formada por seis computadores. Cada computador é conectado diretamente a zero ou mais outros computadores. Mostre que há pelo menos dois computadores na rede que estão diretamente conectados ao mesmonúmero de outros computadores. [Dica:É impossível ter um computador não ligado a nenhum dos outros e um computador ligado a todos os outros.]
Passo 1
Resumindo o enunciado: temos uma rede com 6 computadores, que formam um grafo simples com 6 vértices. Cada vértice tem grau entre 0 e 5 (número de conexões diretas). Queremos mostrar que existem pelo menos dois vértices com o mesmo grau. O conteúdo aqui é o Princípio da Casa dos Pombos.
Passo 2
Observe que, em um grafo com 6 vértices sem laços nem arestas múltiplas, o grau de cada vértice pertence ao conjunto
Passo 3
Graças à dica, notamos que não podem coexistir na rede um vértice de grau
e outro de grau
: se houver um vértice de grau
, ele está ligado a todos os outros, então não existe vértice isolado (grau
); se houver um vértice isolado, nenhum outro pode ter grau
. Logo, dentre os 6 vértices só podem aparecer ao máximo 5 valores distintos de grau.
Passo 4
Pelo Princípio da Casa dos Pombos, se temos 6 vértices (pombos) e no máximo 5 valores de grau possíveis (casas), então dois vértices devem ocupar a mesma “casa” de grau. Ou seja, há pelo menos dois computadores com o mesmo número de conexões.
Resposta
Existem pelo menos dois computadores que estão diretamente conectados a exatamente o mesmo número de outros computadores.