*6. Suponha que
sejam
inteiros positivos com soma
. Mostre que existe uma árvore que tem
vértices tal que o grau desses vértices sejam
.
Passo 1
Resumindo o enunciado: temos
inteiros positivos
cuja soma é
, e queremos construir uma árvore com
vértices cujos graus sejam exatamente esses
. O conteúdo é teoria de grafos, em especial sequências de graus de árvores, lembrando que em toda árvore com
vértices a soma dos graus é
.
Passo 2
Vamos provar o resultado por indução em
.
Passo 3
Caso base
: então
e cada
, logo
. Basta, portanto, tomar os dois vértices e ligá-los por uma aresta; dessa forma obtemos a árvore desejada.
Passo 4
Passo indutivo: suponha que todo conjunto de
inteiros positivos somando
seja realizável como graus de alguma árvore. Agora considere
inteiros positivos somando
. Se todos os
, então a soma seria
, contradição. Logo existe um índice
tal que
. Como a soma
, existe também um índice
com
.
Passo 5
Conecte o vértice
ao vértice
por uma aresta e remova
do conjunto, diminuindo
em 1. Obtemos assim
inteiros positivos
cuja soma é
Pela hipótese de indução existe uma árvore
com esses graus. Basta então ligar de volta o vértice
como folha em
; isso aumenta o grau de
para 1 e restaura o grau de
para
, completando a construção.
Resposta
Concluímos, por indução, que para toda sequência de inteiros positivos com soma
existe uma árvore com
vértices cujos graus são exatamente esses números.