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 G 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 G, todo vértice tem grau \ge1. 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 v, que denotamos \deg(v), satisfaz
1 \le \deg(v) \le 5.
Logo, existem exatamente 5 valores possíveis para \deg(v): o conjunto \{1,2,3,4,5\}.

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.

Exercícios relacionados