Order of a cycle containing four vertices of degree two in $G\Box H$ Suppose the undirected graph $G$ has a vertex $g$ adjacent to the vertices $g_1$ and $g_2$ of degree one and another undirected graph $H$ has a vertex $h$ adjacent to the vertices $h_1$ and $h_2$ of degree one. Then what are the possible orders of a cycle in $G\Box H$ that contains all four of the vertices $(g_1,h_1)$, $(g_1,h_2)$, $(g_2,h_1) $ and $(g_2,h_2)$ ?
By experiment I think the only possible order is $8$, but have not been able to prove it rigorously. 
For the definition of $G\Box H$ see here: http://en.wikipedia.org/wiki/Cartesian_product_of_graphs 
 A: Let $v_{ij}=\langle g_i,h_j\rangle$ for $i,j\in\{1,2\}$. The only vertices adjacent to $v_{ij}$ in $G\,\square\,H$ are $\langle g_i,h\rangle$ and $\langle g,h_j\rangle$, so any cycle containing $v_{ij}$ must sandwich it between $\langle g_i,h\rangle$ and $\langle g,h_j\rangle$. Thus, any cycle containing all four of the $v_{ij}$ must include the following four paths:
$$\begin{align*}
&\langle g_1,h\rangle,v_{11},\langle g,h_1\rangle\\
&\langle g_1,h\rangle,v_{12},\langle g,h_2\rangle\\
&\langle g_2,h\rangle,v_{21},\langle g,h_1\rangle\\
&\langle g_2,h\rangle,v_{22},\langle g,h_2\rangle
\end{align*}\tag{1}$$
In order to extend the first path to the right, we must find another segment containing $\langle g,h_1\rangle$. There is only one, the third in $(1)$, so the only possible extension is
$$\langle g_1,h\rangle,v_{11},\langle g,h_1\rangle,v_{21},\langle g_2,h\rangle\;.\tag{2}$$
The only other appearance of $\langle g_2,h\rangle$ is in the fourth row of $(1)$, so $(2)$ has only one possible extension to the right:
$$\langle g_1,h\rangle,v_{11},\langle g,h_1\rangle,v_{21},\langle g_2,h\rangle,v_{22},\langle g,h_2\rangle\;.\tag{3}$$
Finally, the third row of $(1)$ is the only possible extension of $(3)$ to the right, and it closes the cycle:
$$\langle g_1,h\rangle,v_{11},\langle g,h_1\rangle,v_{21},\langle g_2,h\rangle,v_{22},\langle g,h_2\rangle,v_{12},\langle g_1,h\rangle\;.$$
Thus, this is indeed the only cycle containing all four of the $v_{ij}$.
