Mostre que se um grafo bipartido é
-regular (todos os vértices têm grau
) e tal que a partição
, então
.
Passo 1
Beleza, vamos recapitular o que o exercício pede: temos um grafo
que é bipartido, ou seja, os vértices estão divididos em duas partes
e
, sem arestas “dentro” de cada parte. Além disso ele é
-regular, ou seja, todo vértice (tanto de
quanto de
) tem grau exatamente
. A meta é mostrar que, sob essas condições, o número de vértices em
é igual ao número de vértices em
:
Conteúdo envolvido: ideia de contar arestas de dois jeitos (Lema do Aperto de Mão) e usar a regularidade para traduzir soma de graus em
e
.
Passo 2
Lema do Aperto de Mão (ou Handshake Lemma):
Em qualquer grafo, se você soma todos os graus dos vértices, você conta cada aresta duas vezes (porque cada aresta toca dois vértices). Então vale:
Em qualquer grafo, se você soma todos os graus dos vértices, você conta cada aresta duas vezes (porque cada aresta toca dois vértices). Então vale:
No caso de um grafo bipartido
, todas as arestas vão de
para
. Isso significa que
são duas maneiras de contar exatamente as mesmas arestas, ou seja, cada uma dessas somas vale
.
Passo 3
Agora aplicamos a regularidade
-regular:
- Como todo vértice de
tem grau , - Do mesmo jeito, todo vértice de
tem grau , então
Mas, pelo que falamos no passo anterior, cada uma dessas somas também é igual a
. Logo:
Passo 4
Chegamos à equação
Como estamos falando de
-regular com arestas de verdade, normalmente tomamos
. Assim, dá para dividir ambos os lados por
sem medo de dar divisão por zero. Fica então
Resposta
Portanto, em qualquer grafo bipartido
-regular, as duas partes da bipartição têm a mesma quantidade de vértices: