Para quais valores de
e
o grafo bipartido completo
tem um ciclo hamiltoniano?
Passo 1
O enunciado pergunta para quais inteiros não negativos
e
o grafo bipartido completo
admite um ciclo hamiltoniano, ou seja, um ciclo que passe por todos os seus vértices exatamente uma vez. O conteúdo envolve propriedades de grafos bipartidos e ciclos que percorram todos os vértices.
Passo 2
Em um grafo bipartido qualquer, todos os ciclos têm comprimento par porque eles devem alternar vértices entre as duas partições. Se existe um ciclo hamiltoniano em
, seu comprimento é o número total de vértices:
e
precisa ser par.
Passo 3
Como
deve ser par, isso implica apenas que
e
têm a mesma paridade (ambos pares ou ambos ímpares), mas ainda não garante a existência do ciclo hamiltoniano.
Passo 4
Num ciclo hamiltoniano em um grafo bipartido, como se alterna entre um vértice da partição de tamanho
e um da partição de tamanho
, necessariamente o número de vértices em cada partição é igual. Logo, para usar todos os vértices,
Passo 5
Além disso, para haver ciclo precisamos de pelo menos 3 vértices totais. Em
um ciclo de comprimento
existe apenas se cada vértice tiver grau
, ou seja,
. Para
temos só dois vértices e não há ciclo.
Resposta
O grafo
tem ciclo hamiltoniano se, e somente se,