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 G com \Delta(G)\le2 e uma árvore geradora T\subseteq G em que cada vértice tem grau em T no máximo 2. Queremos mostrar que T é um caminho que passa por todos os vértices de G, ou seja, um caminho hamiltoniano. Para isso vamos usar o Lema do Aperto de Mãos (soma de graus = 2|E|) e a caracterização das árvores de grau máximo 2.

Passo 2

Em toda árvore com n vértices vale o Lema do Aperto de Mãos:
\sum_{v\in V(T)}\deg_T(v)\;=\;2\,|E(T)|\;=\;2\,(n-1).
Como em T temos \deg_T(v)\le2 para todo v, a soma dos graus satisfaz
\sum_{v\in V(T)}\deg_T(v)\le2n.
Mas sabemos que \sum\deg_T(v)=2(n-1)=2n-2, logo a soma atinge exatamente 2n-2, isto é, é 2 unidades menor que o máximo possível 2n.

Passo 3

Para que a soma dos n graus seja 2n-2 e cada grau não ultrapasse 2, só há uma forma: exatamente dois vértices têm grau 1 (as folhas) e os outros n-2 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.

Passo 4

Como T é geradora, ela contém todos os n vértices de G. E vimos que T é um caminho simples que visita cada vértice exatamente uma vez. Essa é precisamente a definição de caminho hamiltoniano em G.

Resposta

A árvore geradora de grau restrito de G é um único caminho hamiltoniano em G.

Exercícios de Livros Relacionados