Condition for Bipartite Graph to be Hamiltonian

Theorem

Let $G = \left({A|B, E}\right)$ be a bipartite graph.

Let $G$ be Hamiltonian.

Then $|A| = |B|$.

That is, there is the same number of vertices in $A$ as there are in $B$.

Proof

To be Hamiltonian, a graph $G$ needs to have a Hamilton cycle, i.e. one which goes through all the vertices of $G$.

As each edge in $G$ connects a vertex in $A$ with a vertex in $B$, any cycle alternately passes through a vertex in $A$ then a vertex in $B$.

Let $G = \left({A|B, E}\right)$ be a bipartite graph.

Suppose WLOG that $|A| > |B|$, i.e. there are more vertices in $A$ than in $B$.

Let $|A| = m, |B| = n$.

Suppose $G$ has a Hamilton cycle $C$.

Let us start tracing that cycle at $u \in B$.

After $2n$ edges have been traversed, we will have arrived back at $u$ again, and all the vertices of $B$ will have been visited.

But there will still be $m - n$ vertices in $A$ which can not have been visited.

Hence $C$ can not be a Hamilton cycle.

$\blacksquare$

Note

The implication does not go both ways.

This graph:

clearly fulfils the conditions (i.e. bipartite graph such that $|A| = |B|$) and is equally clearly not Hamiltonian.