For which values of 𝑚 and 𝑛 does the complete bipartite graph 𝑘𝑚,𝑛 have a…

Answer: K_{m,n} has a Hamiltonian circuit precisely when m = n and m,n ≥ 2.

• Necessity (equal part sizes): In any cycle of a bipartite graph vertices alternate between the two parts. To include every vertex in a single cycle, the cycle must visit each part the same number of times, so the two parts must have equal size (m = n).

• Necessity (minimum degree 2): Every vertex on a cycle has two distinct neighbors, so each vertex must have degree at least 2. In K_{m,n} the degrees are n and m, so we require m ≥ 2 and n ≥ 2.

• Sufficiency (construction): When m = n = k ≥ 2, label vertices in the two parts a1,...,ak and b1,...,bk. The cycle a1 - b1 - a2 - b2 - ... - ak - bk - a1 visits every vertex exactly once and is a Hamiltonian circuit.

• Conclusion: K_{m,n} has a Hamiltonian circuit if and only if m = n and m,n ≥ 2.