Let $\Gamma=(V,E)$ be a complete bipartite graph with bipartition $V=R\cup B$.
Show that if $\Gamma$ is hamiltonian then $|R|=|B|$.
My attempt:
Suppose $\Gamma$ is hamiltonian. Put $|R|=m$ and $|B|=n$. For an absurdity, suppose $m<n$.
Let $r_1,……,r_m$ be the vertices in $R$ and $b_1,……,b_n$ the vertices in $B$.
Since $\Gamma$ is hamiltonian, we have a hamiltonian cycle. Suppose that cycle starts at $r_1$. We may without loss of generality assume the cycle takes the form
$$r_1b_1 b_1r_2 r_2b_3 b_3r_3r_3b_4…….r_mb_m…..b_kr_1$$ where $1\leq k \leq n$. If $k>m$ then there must exist some $1\leq j \leq m$ such that $r_jb_k$ is an edge. Since a cycle has distinct vertices, this is a contradiction. Hence $k\leq m$. However, if $k\leq m$, then $k$ is any of $1,2,3,……$. This again implies that the hamiltonian cycle contains repeating vertices and thus we obtain another contradiction.
Is this correct?
Best Answer
No, your proof is not quite correct. Indeed, it doesn't really use the assumption that $m < n$; but without this assumption there is no contradiction, so something must be wrong.
The problem is that from $k \leq m$ we cannot deduce that your Hamiltonian circuit contains repeated vertices; this would be true for $k < m$, but for $k = m$ you have a problem. You should rather use the observation that a Hamiltonian circuit must contain all vertices of $B$, so, in particular, we must have $\{b_1, \dots, b_k\} = B$. But this implies that $k = n$, contradicting $k \leq m$.