Given a rectangular grid of dimensions $5 \times 9$, find if it contains any Hamiltonian cycle in it or not. Can the result be generalized for dimensions $m \times n.$
Example
I have tried making grids on paper and found that Hamiltonian circuits are easy to build if any(or both) of the dimensions are even, however I couldn't prove and generalize my observation.
Any help is much appreciated.