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.)
(Sugestão: considere separadamente nó(s) de grau zero.)
Passo 1
Resumindo, temos um grafo simples
com
nós, onde
. 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
o conjunto de nós de
e para cada nó
definimos
como o número de arestas incidentes em
. Como
é simples, o grau de qualquer nó varia entre
e
. Assim, o conjunto de valores possíveis de grau é
Porém, não podemos usar todos esses
valores simultaneamente, pois há uma incompatibilidade entre grau zero e grau
.
Passo 3
Separaremos em dois casos:
- Se não existe nenhum nó de grau zero, então todo nó tem grau pelo menos
. Logo os graus estão contidos em
que são exatamente
valores possíveis para
nós.
2. Se existe pelo menos um nó de grau zero, então nenhum nó pode ter grau (pois um nó de grau
estaria conectado a todos os outros, inclusive a esse de grau zero). Assim os graus estão contidos em
2. Se existe pelo menos um nó de grau zero, então nenhum nó pode ter grau
também
valores possíveis para
nós.
Passo 4
Em cada caso acabamos com
nós (pombos) distribuídos em apenas
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
e
tais que
Resposta
Em todo grafo com pelo menos dois nós existem sempre dois nós com o mesmo grau.