Mostre que uma árvore geradora de grau restrito de um grafo simples, no qual cada vértice tem grau que não exceda a 2, consiste em um único caminho hamiltoniano no grafo.
Passo 1
O enunciado diz que temos um grafo simples
com
e uma árvore geradora
em que cada vértice tem grau em
no máximo 2. Queremos mostrar que
é um caminho que passa por todos os vértices de
, ou seja, um caminho hamiltoniano. Para isso vamos usar o Lema do Aperto de Mãos (soma de graus =
) e a caracterização das árvores de grau máximo 2.
Passo 2
Em toda árvore com
vértices vale o Lema do Aperto de Mãos:
Como em
temos
para todo
, a soma dos graus satisfaz
Mas sabemos que
, logo a soma atinge exatamente
, isto é, é 2 unidades menor que o máximo possível
.
Passo 3
Para que a soma dos
graus seja
e cada grau não ultrapasse 2, só há uma forma: exatamente dois vértices têm grau 1 (as folhas) e os outros
vértices têm grau 2.
Uma árvore conexa em que há exatamente duas folhas e todos os demais vértices têm grau 2 é, por definição, um caminho simples que vai de uma folha até a outra.
Uma árvore conexa em que há exatamente duas folhas e todos os demais vértices têm grau 2 é, por definição, um caminho simples que vai de uma folha até a outra.
Passo 4
Como
é geradora, ela contém todos os
vértices de
. E vimos que
é um caminho simples que visita cada vértice exatamente uma vez. Essa é precisamente a definição de caminho hamiltoniano em
.
Resposta
A árvore geradora de grau restrito de
é um único caminho hamiltoniano em
.