Prove que
, o grafo completo em
vértices, tem um circuito hamiltoniano para todo
.
Passo 1
O enunciado pede para mostrar que o grafo completo em
vértices, denotado por
, sempre contém um circuito hamiltoniano sempre que
. 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
, há aresta entre qualquer par de vértices.
Passo 2
Liste os vértices de
de forma arbitrária como
Por definição, em
existe aresta entre
e
para todos
.
Passo 3
Considere o trajeto
Para cada
temos aresta
, e também existe aresta
.
Passo 4
Esse caminho visita cada vértice
exatamente uma vez e retorna a
, satisfazendo a definição de circuito hamiltoniano.
Resposta
Portanto, para todo
, o grafo completo
possui um circuito hamiltoniano.