O Princípio da Casa dos Pombos – Aplicação em Grafos

Estava relendo o excelente artigo “O Princípio da Casa dos Pombos“, publicado pelo Reston aqui no blog e me lembrei de um problema em grafos que pode ser provado matemáticamente, de forma bastante elegante, utilizando-se este princípio.

Antes de falar sobre o problema, vamos primeiro recordar brevemente algumas definições sobre grafos (para maiores detalhes, existe um artigo que explora estas definições mais profundamente aqui):

Um grafo é um par ordenado (V,A), onde V e A são conjuntos disjuntos e cada elemento de A corresponde a um par não-ordenado de elementos (não necessariamente distintos) de V. Os elementos do conjunto V são chamados vértices e os elementos do conjunto A são chamados arestas.

Se G é um grafo, então denotamos seu conjunto de vértices por V(G), e o seu conjunto de arestas por A(G).

Além disso, vamos nos recordar brevemente do que é o princípio da casa dos pombos:

Imagine que você está sentado em um banco de praça, num belo domingo ensolarado. A certa altura, você percebe, e começa a contar, o número de pombos que está procurando comida na sua frente. Ao todo, você conta 10 pombos. Entretanto, uma motocicleta passa em alta velocidade e, com o barulho feito, assusta os dez pombos que voam para um pombal com 9 casas. Eles entram e se escondem por lá.

Sabendo que nenhum pombo desviou a direção, o que você pode concluir? Bem, se dez pombos entraram em 9 casas, podemos concluir que em pelos menos 1 casa esconderam-se 2 pombos!

Agora que refrescamos alguns princípios em nossa mente, vamos falar sobre o problema, que se resume a uma simples pergunta: “É verdade que todo grafo com pelo menos dois vértices tem dois vértices com o mesmo numero de vizinhos?”

A resposta é: Sim.

Prova por contradição: Suponha que exista um grafo G, com vértices {v1,v2,… vn}, tal que, os graus dos vértices em G sejam da seguinte forma: d(vn) = (n – 1), d(vn-1) = (n – 2), … , d(v1) = 0. Ora, isso é um absurdo, pois se d(vn) = (n – 1), vn tem vizinhança com todos os vértices em G, e, portanto v1 não pode ter grau 0.