Você pode encontrar um grafo simples com n vértices com n \geq 3 que não tenha um ciclo hamiltoniano, mas que o grau de cada vértice no grafo seja, pelo menos, (n-1) / 2 ?

Passo 1

O enunciado pede um grafo simples G com n\ge3 vértices, sem ciclo hamiltoniano, mas com grau mínimo
\delta(G)\ge\frac{n-1}2.
O conteúdo envolvido é o Teorema de Dirac e a construção de um contraexemplo quando o limiar é apenas (n-1)/2.

Passo 2

Recordando o Teorema de Dirac: se G tem n\ge3 vértices e
\delta(G)\ge\frac n2,
então G possui ciclo hamiltoniano.

Passo 3

Note que comparar \tfrac{n-1}2 com \tfrac n2 dá:
  • Se n é par, digamos n=2k, então \tfrac{n-1}2=k-\tfrac12 e exigir grau inteiro \ge\lceil k-\tfrac12\rceil=k significa \delta(G)\ge n/2, o que força Hamiltoniano por Dirac.
  • Portanto só faz sentido buscar contraexemplo quando n é ímpar.

Passo 4

Seja n=2k+1 com k\ge1. Vamos construir o grafo completo bipartido
G = K_{k,\;k+1}.

Passo 5

No grafo K_{k,k+1}:
  • Cada vértice da parte de tamanho k tem grau k+1.
  • Cada vértice da parte de tamanho k+1 tem grau k.
    Logo
\delta(G)=k=\frac{n-1}2.

Passo 6

Como G é bipartido, todos os ciclos têm comprimento par. Mas n=2k+1 é ímpar, então não existe ciclo que passe por todos os n vértices. Logo G não tem ciclo hamiltoniano.

Resposta

Para n ímpar, o grafo K_{\frac{n-1}2,\frac{n+1}2} é simples, satisfaz \delta(G)\ge\frac{n-1}2 e não possui ciclo hamiltoniano.

Exercícios de Livros Relacionados