Consider a complete bipartite graph km,n. For which values of m and n does…

Correct condition: A complete bipartite graph K_{m,n} has a Hamiltonian circuit exactly when m = n ≥ 2.

• Necessity: A Hamiltonian circuit visits every vertex once and in a bipartite graph must alternate between the two partite sets. Therefore the two sets must contain the same number of vertices.

• Lower bound: Any cycle in a bipartite graph has even length, so the smallest possible Hamiltonian cycle uses 4 vertices. Thus each part must have at least 2 vertices (n ≥ 2).

• Sufficiency and construction: If m = n = k with k ≥ 2, label the vertices of the two parts u1,…,uk and v1,…,vk. Then the cycle u1–v1–u2–v2–…–uk–vk–u1 is a Hamiltonian circuit that visits every vertex exactly once.

• Examples: K_{2,2} is a 4-cycle (so it has a Hamiltonian circuit). Any K_{n,n} with n ≥ 2 admits the alternating cycle above.