For what values of m and n is the complete bipartite graph K

For what values of m and n is the complete bipartite graph K_m, n regular?

Solution

Suppose if possible assume that m < n.

So, any cycle in the bipartite graph can have atmost 2m vertices (follows from: Any bipartite graph always has an even cycle only).

Hamiltonian cycle must cover all the vertices, so the cycle covers m + n edges.

Also, as stated (m < n), so, n + m > 2m. But, from the earlier result, our bipartite graph can have atmost 2m edges. Which is a contradiction.

So, m = n.

down vote