Uma rede de computadores é formada por seis computadores. Cada computador é conectado diretamente a, pelo menos, um dos outros computadores. Mostre que há pelo menos dois computadores na rede que estão diretamente conectados ao mesmo número de outros computadores.
Passo 1
Vamos modelar a rede de seis computadores como um grafo não dirigido
com seis vértices, onde cada vértice representa um computador e cada aresta representa uma conexão direta entre dois computadores. Como o enunciado diz que cada computador está conectado a pelo menos um outro, concluímos que, em
, todo vértice tem grau
. O que vamos usar aqui é a noção de grau de um vértice em grafos e o Princípio da Casa dos Pombos.
Passo 2
Em qualquer grafo com seis vértices sem vértices isolados, o grau de cada vértice
, que denotamos
, satisfaz
Logo, existem exatamente 5 valores possíveis para
: o conjunto
.
Passo 3
Como temos 6 vértices (os “pombos”) e apenas 5 valores possíveis de grau (as “casas”), o Princípio da Casa dos Pombos garante que pelo menos dois vértices compartilham o mesmo valor de grau.
Resposta
Há pelo menos dois computadores na rede que estão diretamente conectados ao mesmo número de outros computadores.