How to prove that the cartesian product of $2$ grid graphs $P_n$ and $P_q$ (where $n$ and $q$ are odd) is not hamiltonian?

156 Views Asked by At

Let us assume that we have the graph $G$ which is the cartesian product of two grid graphs $P_n$ and $P_q$ wherein $n$ and $q$ are odd, I need to prove that $G$ is never hamiltonian. I am able to verify that for specific cases by plugging the values and checking if the graph consists of a hamiltonian cycle. However, I am unable to figure out a generalized approach for the same.