Give a counter example to show that if $G$ and $H$ are both Eulerian but only one is connected, then the cartesian product is not Eulerian

Question

Well it's easy to prove that if the graphs $G$ and $H$ are both connected and Eulerian then $G\square H$ is Eulerian since for both G and H every vertex has even degree. But this statement is not true when $G$ or $H$ is not connected. There is a clear example of this?

Answer 1

Take $G = H = K_3 \sqcup K_1$: a triangle, together with an isolated vertex. This graph is Eulerian, since going around the triangle is an Eulerian tour. However, it is not connected.

For this example, $G \mathbin{\square} H$ is the following graph:

Since the degree of a vertex $v = (v_G, v_H)$ in $G \mathbin{\square} H$ is $\deg(v_G) + \deg(v_H)$, it is still even. But there are now nontrivial components, so $G \mathbin{\square} H$ has no Eulerian tour.

In general, whenever $G$ has an isolated vertex ($G = G' \sqcup K_1$) and $H$ has any edges, $G \mathbin{\square}H$ will be isomorphic to $(G' \mathbin{\square}H) \sqcup H$, so it will have at least two nontrivial components, and we'll get a counterexample. (Same when the roles of $G$ and $H$ are switched.)