Mostre que se um grafo bipartido é k-regular (todos os vértices têm grau k) e tal que a partição V(G)=X cup Y, então |X|=|Y|.

Passo 1

Beleza, vamos recapitular o que o exercício pede: temos um grafo |X| = |Y| 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:
sumvin V(G) deg(v) ;=; 2,|E(G)|
No caso de um grafo bipartido sumxin X deg(x) e sumyin Y deg(y) , 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 sumxin X deg(x) ;=; k,|X| -regular:
  • Como todo vértice de sumyin Y deg(y) ;=; k,|Y| tem grau k,|X| = |E(G)| = k,|Y| ,
  • 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
k,|X| = k,|Y|
Como estamos falando de |X| = |Y| -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 boxed|X| = |Y| -regular, as duas partes da bipartição têm a mesma quantidade de vértices:

Exercícios relacionados