Você pode encontrar um grafo simples com
vértices com
que não tenha um ciclo hamiltoniano, mas que o grau de cada vértice no grafo seja, pelo menos,
?
Passo 1
O enunciado pede um grafo simples
com
vértices, sem ciclo hamiltoniano, mas com grau mínimo
O conteúdo envolvido é o Teorema de Dirac e a construção de um contraexemplo quando o limiar é apenas
.
Passo 2
Recordando o Teorema de Dirac: se
tem
vértices e
então
possui ciclo hamiltoniano.
Passo 3
Note que comparar
com
dá:
- Se
é par, digamos , então e exigir grau inteiro significa , o que força Hamiltoniano por Dirac. - Portanto só faz sentido buscar contraexemplo quando
é ímpar.
Passo 4
Seja
com
. Vamos construir o grafo completo bipartido
Passo 5
No grafo
:
- Cada vértice da parte de tamanho
tem grau . - Cada vértice da parte de tamanho
tem grau .
Logo
Passo 6
Como
é bipartido, todos os ciclos têm comprimento par. Mas
é ímpar, então não existe ciclo que passe por todos os
vértices. Logo
não tem ciclo hamiltoniano.
Resposta
Para
ímpar, o grafo
é simples, satisfaz
e não possui ciclo hamiltoniano.