*6. Suponha que d_{1}, d_{2}, \ldots, d_{n} sejam n inteiros positivos com soma 2 n-2. Mostre que existe uma árvore que tem n vértices tal que o grau desses vértices sejam d_{1}, d_{2}, \ldots, d_{n}.

Passo 1

Resumindo o enunciado: temos n inteiros positivos \{d_{1},d_{2},\dots,d_{n}\} cuja soma é \sum_{k=1}^{n}d_{k}=2n-2, e queremos construir uma árvore com n vértices cujos graus sejam exatamente esses d_{k}. O conteúdo é teoria de grafos, em especial sequências de graus de árvores, lembrando que em toda árvore com n vértices a soma dos graus é 2(n-1).

Passo 2

Vamos provar o resultado por indução em n.

Passo 3

Caso base n=2: então \sum_{k=1}^{2}d_{k}=2 e cada d_{k}\ge1, logo d_{1}=d_{2}=1. 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 n-1 inteiros positivos somando 2(n-1)-2 seja realizável como graus de alguma árvore. Agora considere n inteiros positivos somando 2n-2. Se todos os d_{k}\ge2, então a soma seria \ge2n>2n-2, contradição. Logo existe um índice i tal que d_{i}=1. Como a soma 2n-2>n, existe também um índice j com d_{j}>1.

Passo 5

Conecte o vértice i ao vértice j por uma aresta e remova i do conjunto, diminuindo d_{j} em 1. Obtemos assim n-1 inteiros positivos \{d'_{1},\dots,d'_{n-1}\} cuja soma é
\sum_{k=1}^{n-1}d'_{k}=(2n-2)-2=2(n-1)-2.
Pela hipótese de indução existe uma árvore T' com esses graus. Basta então ligar de volta o vértice i como folha em j; isso aumenta o grau de i para 1 e restaura o grau de j para d_{j}, completando a construção.

Resposta

Concluímos, por indução, que para toda sequência de inteiros positivos com soma 2n-2 existe uma árvore com n vértices cujos graus são exatamente esses números.

Exercícios de Livros Relacionados