Prove que Kn, o grafo completo em n vértices, tem um circuito hamiltoniano para todo n >= 3.

Passo 1

O enunciado pede para mostrar que o grafo completo em n vértices, denotado por Kn, sempre contém um circuito hamiltoniano sempre que n>=3. O conteúdo aqui é de grafos e, em particular, de ciclos que passam exatamente uma vez por cada vértice (circuito hamiltoniano). Vamos usar o fato de que, em Kn, há aresta entre qualquer par de vértices.

Passo 2

Liste os vértices de Kn de forma arbitrária como
V(Kn) = v1,v2,dots,vn
Por definição, em Kn existe aresta entre vi e vj para todos ineq j.

Passo 3

Considere o trajeto
v1;-;v2;-;cdots;-;vn;-;v1
Para cada i=1,2,dots,n-1 temos aresta vi,vi+1, e também existe aresta vn,v1.

Passo 4

Esse caminho visita cada vértice vi exatamente uma vez e retorna a v1, satisfazendo a definição de circuito hamiltoniano.

Resposta

Portanto, para todo n>=3, o grafo completo Kn possui um circuito hamiltoniano.

Exercícios de Livros Relacionados