How to deduce that $K_{m,n}$ is hamiltonian iff $m = n\ge 2$

Question

I know how to prove that a bipartite graph $G$ with bipartitions $B$ and $W$ must both have the same number of vertices. I am having trouble, though, proving that they must have at least 2 vertices. Any help?

Answer 1

You have two cases: $m \geq n$ or $m = 1, n = 1$. Gerry Myerson covered $K_{1, 1}$ pretty well. Now if $m \geq 1$, pick a vertex $v_{1}$ from the first partition. We consider $n = 2, m = 1$ to demonstrate the concept. It is connected to the only vertex in the second partition. We then pick a different vertex in the first partition. Since no vertices in the first partition are adjacent, and since there is only one vertex in the second partition, it is impossible to return to our starting vertex without re-using the vertex in partition two. This contradicts the definition of a Hamiltonian circuit.