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