Obtenha uma fórmula para o número de
de
.
Passo 1
O enunciado pede a fórmula para o número de arcos do grafo completo bipartido
. Esse grafo tem dois conjuntos de vértices disjuntos, um de tamanho
e outro de tamanho
, e todo vértice de um conjunto está ligado a todos os vértices do outro. Vamos usar uma contagem simples de quantas ligações existem entre os dois conjuntos.
Passo 2
Definimos os dois conjuntos de vértices como
e
Por construção de
, não há arcos entre vértices de
nem entre vértices de
, apenas entre um vértice de
e um de
.
Passo 3
Escolhendo um vértice fixo em
, esse vértice se conecta a todos os
vértices de
. Logo, cada vértice de
proporciona
arcos.
Passo 4
Como existem
vértices em
e cada um gera
arcos distintos (não há sobreposição porque não há arcos dentro de
), o total de arcos é