Skip to content
Quantoros

For positive m,n, when does complete bipartite K(m,n) have a Hamiltonian path? When does it have a Hamiltonian cycle?

Quant ResearchLevel: IntermediateAlternating path constraint

For positive m,n, when does complete bipartite K_(m,n) have a Hamiltonian path? When does it have a Hamiltonian cycle?

Hints
  • Write the sequence of part labels along a path.
  • A cycle must return with the same alternating balance.

Answer

A path alternates parts, so their sizes differ by at most one; completeness makes this sufficient. A cycle requires equal sizes and m=n>=2. For m=n=1 there is an edge path, not a simple cycle.

Source and licence: Oscar Levin — Discrete Mathematics: An Open Introduction, 3rd edition · CC-BY-SA-4.0 · answer: Quantoros editorial

Related questions