Obtenha uma fórmula para o número de \operatorname{arcos} de K_{n, \ell}.

Passo 1

O enunciado pede a fórmula para o número de arcos do grafo completo bipartido K_{n,\ell}. Esse grafo tem dois conjuntos de vértices disjuntos, um de tamanho n e outro de tamanho \ell, 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
A\quad\text{com}\quad |A|=n
e
B\quad\text{com}\quad |B|=\ell.
Por construção de K_{n,\ell}, não há arcos entre vértices de A nem entre vértices de B, apenas entre um vértice de A e um de B.

Passo 3

Escolhendo um vértice fixo em A, esse vértice se conecta a todos os \ell vértices de B. Logo, cada vértice de A proporciona \ell arcos.

Passo 4

Como existem n vértices em A e cada um gera \ell arcos distintos (não há sobreposição porque não há arcos dentro de A), o total de arcos é
n \times \ell.

Resposta

\;n\ell

Exercícios de Livros Relacionados