Cartesian product of Hamiltonian graphs Prove that cartesian product of 2 Hamiltonian graphs is also Hamiltonian.
Also please explain the significance of cartesian product of 2 graphs
 A: Here's a pair of big hints which will get you started in the right direction.
First suppose that $G_1$ has $m$ vertices and $G_2$ has $n$ vertices.  You can view $G_1\square G_2$ as an $m\times n$ grid of vertices.  In each column is a copy of $G_1$ in each row is a copy of $G_2$.  It will help your understanding if you draw a few examples, draw the product of short two short paths, maybe the product of two small cycles, maybe a path and a cycle.  That'll give you decent enough intuition to answer the question.
Second, if $G_1$ has $m$ vertices and is Hamiltonian, then $C_m$ (the cycle on $m$ vertices) is a subgraph of $G_1$.  Likewise, if $G_2$ has $n$ vertices and is Hamiltonian then $C_n$ is a subgraph of $G_2$.  This implies that $C_m\square C_n$ is a subgraph of $G_1\square G_2$.  Then, all you need to show is that $C_m\square C_n$ is Hamiltonian and you are done (because you find the Hamiltonian cycle in a subgraph of $G_1\square G_2$).  Your intuition from step 1 will help a lot with step 2.
