Consider a graph $G$. As usual, denote a path graph of length $n$ as $P_{n}$, and $\times$ is for Cartesian product of graph. If $G$ is Hamiltonian (ie. have a Hamiltonian cycle) then it is easy to prove that $G\times P_{n}$ is always Hamiltonian. The question is about when $G$ is not Hamiltonian. What are the possible value of $n$ such that $G\times P_{n}$ is Hamiltonian.
My attempt so far: the set of possible $n$ is closed under addition.
Okay, I doodled around and can show, that this will not work for arbitrary graphs. Take $G$ to be the three pointed star $K_{1,3}$ with center vertex $c$ and "points" $a_1,a_2,a_3$. And let $P_n$ be the path with vertices $p_1,...,p_n$. Then $G\times P_n$ is not hamiltonian for any n, since the three vertices $(a_i,p_1)$ are all of degree 2 and connected to $(c,p_1)$. So any Hamiltonian cycle would have to use all of the edges belonging to those nodes including $((a_i,p_1),(c,p_1))$, so there are three edges in the cycle that have $(c,p_1)$ as a node, which is a contradiction.