in an $m \times n$ grid, prove that if $m$ and $n$ are odd, then there is no hamiltonian cycle [duplicate]

Question

Let a simple undirected graph $G=(V,E)$ be defined by $V=\{1,2,...,m\} \times \{1,2,...,n\}$ and $E=E_1 \cup E_2$ where $$\begin{split} E_1 &= \{((a,b),(a+1&,b&)) &\; | 1 \leq a \leq m-1 &,\; 1 \leq b \leq n &\} \\ E_2 &= \{((a,b),(a&,b+1&)) &\; | 1 \leq a \leq m &,\; 1 \leq b \leq n-1 &\} \end{split}$$

Prove that if $2 \leq m, 2 \leq n$ and $2 \not| mn$, then there doesn't exist a Hamiltonian cycle in $G$.

this question came right after the question: "Prove that if $2 \leq m,2 \leq n$ and $2 | mn$, then in $G$ there is a Hamiltonian cycle. A question that I solved. Maybe someone could use that question to answer this one.

Now here is what I think to use for the main question:

I tried using the fact (*) that the graph is bipartite. Maybe I can do something with the 2 sides of the bipartite graph having to be equal for a Hamiltonian cycle? I now come back to this question, I think I can do this: Since $m,n$ is odd, then $|V|=mn$ is also odd, which means there cannot be 2 equal sides in the bipartite graph, which means it doesn't have a hamiltonian cycle.

I can't find my class notes right now, so if someone can confirm that theorem (*) is indeed correct, that would be great. And if not, then someone help me out here please

Answer 1

For $m$ and $n$ both being odd, color the grid like a chessboard. Say the corners are all white. The number of white cells are $1$ more than the number of black cells.

Any Hamiltonian cycle would traverse an equal number of white and black cells, so there cannot be any.