Prove: G is Bipartite with bipartition(x,y) where |x| not equal |y|, then G is nonhamiltonian?

Question

Note: since G is bipartite it contains no odd cycles

Answer 1

A Hamiltonian cycle would have to be a sequence of edges $\{z_1,z_2\},\{z_2,z_3\},\{z_3,z_4\},\ldots,\{z_{n-1},z_n\},\{z_n,z_1\}$ such that each vertex of the graph is equal to exactly one $z_i$ (that is, the cycle visits each vertex exactly once). Assume that $z_1\in x$. Since the graph is bipartite, we must have that $z_2\in y$. In general, $z_{2i-1}\in x$ and $z_{2i}\in y$ for all $i$ because the edges must alternate between $x$ and $y$. Again by the bipartite property we must have that $z_n\in y$ since $z_1\in x$ and the edge $\{z_n,z_1\}$ is contained in the cycle. Recalling that the elements of $y$ have even indices, this implies that there are an even number of vertices. The odd-indexed vertices are in $x$, and the even-indexed vertices are in $y$. Therefore $|x|=|y|$ if a Hamiltonian cycle exists.

Answer 2

Suppose $G$ is bipartite with bipartition $(X,Y)$ and has a hamilton cycle. We show $|X|=|Y|$. Any cycle in a bipartite graph has its vertices alternating between being in $X$ and being in $Y$, and hence any cycle contains an equal number of vertices from $X$ and $Y$. In addition, a hamilton cycle also contains all the vertices of the graph. Hence the total number of vertices in $X$ is equal to the total number of vertices in $Y$.