É verdade que todo grafo com pelo menos dois vértices tem dois vértices com o mesmo número de vizinhos? Em outras palavras, se um grafo tem mais de um vértice, é verdade que existem dois vértices distintos v e w tais que |Gamma(v)|=|Gamma(w)| ? (Uma maneira mais informal de dizer isso é: é verdade que em toda cidade com pelo menos dois habitantes residem duas pessoas que têm exatamente o mesmo número de amigos na cidade?).

Passo 1

Beleza, vamos lá! A questão pergunta se em qualquer grafo com pelo menos dois vértices, sempre existem dois vértices que têm o mesmo número de vizinhos. Em termos de teoria dos grafos, estamos falando sobre graus dos vértices. Para resolver isso, vamos precisar entender o Princípio da Casa dos Pombos e como ele se aplica aos grafos.

Passo 2

Primeiro, vamos lembrar que em um grafo com vértices, o grau de um vértice é o número de arestas que ele tem, ou seja, quantos vizinhos ele possui. Esses graus podem variar de 0 (se o vértice não estiver conectado a nenhum outro) até (se estiver conectado a todos os outros vértices).

Passo 3

Agora, vamos trazer o Princípio da Casa dos Pombos, que basicamente diz que se você tem mais “pombos” (no nosso caso, vértices) do que “casas” (possíveis graus), pelo menos dois pombos terão que estar na mesma casa.

Passo 4

No nosso grafo, os possíveis graus vão de 0 a . Isso dá um total de possíveis valores de grau. Mas aqui vem o truque: se um vértice tem grau 0, isso significa que ele não está conectado a ninguém. Por outro lado, se um vértice tem grau , ele está conectado a todos os outros vértices, o que implicaria que não pode haver nenhum vértice com grau 0 nesse grafo.

Passo 5

Então, na verdade, os graus possíveis são de 0 a ou de 1 a , mas nunca ambos ao mesmo tempo. Isso significa que existem apenas valores distintos de grau possíveis para os vértices.

Passo 6

Aplicando o Princípio da Casa dos Pombos aqui, como temos vértices e apenas possíveis diferentes graus, necessariamente pelo menos dois vértices devem compartilhar o mesmo grau.

Resposta

Sim, todo grafo com pelo menos dois vértices possui dois vértices com o mesmo número de vizinhos.

Exercícios relacionados