Para quais valores de m e n o grafo bipartido completo K_{m, n} tem um ciclo hamiltoniano?

Passo 1

O enunciado pergunta para quais inteiros não negativos m e n o grafo bipartido completo K_{m,n} 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 K_{m,n}, seu comprimento é o número total de vértices:
\ell = m + n
e \ell precisa ser par.

Passo 3

Como \ell = m + n deve ser par, isso implica apenas que m e n 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 m e um da partição de tamanho n, necessariamente o número de vértices em cada partição é igual. Logo, para usar todos os vértices,
m = n.

Passo 5

Além disso, para haver ciclo precisamos de pelo menos 3 vértices totais. Em K_{m,m} um ciclo de comprimento 2m existe apenas se cada vértice tiver grau >=2, ou seja, m\ge2. Para m=1 temos só dois vértices e não há ciclo.

Resposta

O grafo K_{m,n} tem ciclo hamiltoniano se, e somente se,
m = n \quad\text{e}\quad m\ge2.

Exercícios de Livros Relacionados