Utilize o princípio da casa dos pombos para mostrar que pelo menos dois nós têm o mesmo grau num grafo que contenha pelo menos dois nós.
(Sugestão: considere separadamente nó(s) de grau zero.)

Passo 1

Resumindo, temos um grafo simples G com n nós, onde n\ge2. Queremos mostrar, usando o princípio da casa dos pombos (pigeonhole principle), que existem ao menos dois nós com o mesmo grau. O conteúdo principal aqui é justamente o princípio da casa dos pombos aplicado ao conjunto de valores possíveis de grau de cada nó.

Passo 2

Seja V o conjunto de nós de G e para cada nó v\in V definimos \deg(v) como o número de arestas incidentes em v. Como G é simples, o grau de qualquer nó varia entre 0 e n-1. Assim, o conjunto de valores possíveis de grau é
\{0,1,2,\dots,n-1\}.
Porém, não podemos usar todos esses n valores simultaneamente, pois há uma incompatibilidade entre grau zero e grau n-1.

Passo 3

Separaremos em dois casos:
  1. Se não existe nenhum nó de grau zero, então todo nó tem grau pelo menos 1. Logo os graus estão contidos em
\{1,2,\dots,n-1\},
que são exatamente n-1 valores possíveis para n nós.
2. Se existe pelo menos um nó de grau zero, então nenhum nó pode ter grau n-1 (pois um nó de grau n-1 estaria conectado a todos os outros, inclusive a esse de grau zero). Assim os graus estão contidos em
\{0,1,2,\dots,n-2\},
também n-1 valores possíveis para n nós.

Passo 4

Em cada caso acabamos com n nós (pombos) distribuídos em apenas n-1 valores de grau (caixas). Pelo princípio da casa dos pombos, ao menos uma caixa conterá pelo menos dois pombos. Ou seja, existem dois nós distintos u e v tais que
\deg(u)=\deg(v).

Resposta

Em todo grafo com pelo menos dois nós existem sempre dois nós com o mesmo grau.

Exercícios de Livros Relacionados