Find a necessary and sufficient condition for the Cartesian product $G \times H$ is Eulerian, for $G$ and $H$ are non trivial connected graphs.

Question

Find a necessary and sufficient condition for the Cartesian product $G \times H$ is Eulerian, for $G$ and $H$ are non trivial connected graphs.

I know that if every vertex in $H$ and $G$ are both odd then when you Cartesian them, you have odd plus odd is even, so $G\times H$ contain all even vertices, thus Eulerian.

Same thing happen when both $H$ and $G$ contain all even vertices.

However, I don't know how to make a formal argument for these claim.

Answer 1

You already answered by yourself.

A connected graph is Eulerian if and only if every node has even degree.

We know that if $(u,v)$ is a node in the product, then $\;\deg(u,v)=\deg(u)+\deg(v)\;$, and it is connected if and only if the two graph are connected.

Let's prove that

The cartesian product of two connected graph is Eulerian if and only 
if both graphs have all nodes with the same degree parity.

Let's suppose the product to be Eulerian, that is, all his nodes have even degree.
Taken $u,u'$ in $G$ and $v,v'$ in $H$ four nodes, then
$$ \deg(u)+\deg(v)\\ \deg(u')+\deg(v)\\ \deg(u)+\deg(v')\\ \deg(u')+\deg(v') $$ must be even, so also $$ \deg(u)-\deg(u')\\ \deg(v)-\deg(v') $$ must be even, so all nodes have the same degree parity, meaning they're all odd or they're all even.

Conversely, supposing all nodes have the same degree parity, it's obvious that the cartesian product is Eulerian.