If two graphs are planar, will the cartesian product between them be planar? I think this question is false, but I am not sure how to prove it. I found the product of two 3-cycles (see diagram). But I don't know how to prove it can't be planar. It passes Euler's formula. I have tried looking for subgraphs that fail the test, but am not finding any. 
 A: I can find a subdivision of a $K_5$ in your graph.  Four of the edges are subdivided.  Remember that in Kuratowski's theorem we need not find a $K_5$ subgraph, merely a subdivision of a $K_5$ to conclude that it is not planar.  Labeling the vertices $a,b,c,\dots$ instead and removing unnecessary edges:

As there is a $K_5$ subdivision as a subgraph, your original graph too therefore cannot be planar.
A: Another counterexample is the hypercube $Q_{d}$ for $d \geq 4$. We note that $Q_{d} = \prod_{i=1}^{d} K_{2}$. In particular, $Q_{4} = Q_{3} \times K_{2}$, and both $Q_{3}, K_{2}$ are planar.
A: If we take the Cartesian product of $K_4$ and $K_2$ (both planar), then by identifying the vertices in one of the copies of $K_4$, we get a $K_5$ minor.  Wagner's theorem thus implies it's non-planar.
Another counterexample is the Cartesian product of $K_4$ and $K_4$.  It has $v=16$ vertices and $e=48$ edges, but this does not satisfy $e \leq 3v-6$, which is required by Euler's formula for planar graphs.
