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
\{0,1,2,3,4,5\}.

Passo 3

Graças à dica, notamos que não podem coexistir na rede um vértice de grau 0 e outro de grau 5: se houver um vértice de grau 5, ele está ligado a todos os outros, então não existe vértice isolado (grau 0); se houver um vértice isolado, nenhum outro pode ter grau 5. 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.

Exercícios relacionados