Q: $K_m \mathop{\square} K_n$ contains an Eulerian circuit Prove that $mn$ when $K_m \mathop{\square} K_n$ (Cartesian graph product) contains an Eulerian circuit if and only if $mn\equiv1\pmod 4 $ and both $m,n \gt 1$. 
Attempt:
Assume vertex set of the product graph as $(m)\square (n)$
Assume edge set of the product graph as  $(u_1,v_1)$ is adjacent to $(u_2,v_2)$. 
The edge will be adjacent if :
$u_1=u_2$ then $v_1$ is adjacent to $v_2$ 
$v_1=v_2$ then $u_1$ is adjacent to $u_2$ 
Two vertices of a complete graph will adjacent if they are not equal, so the degree of any vertex of the product graph is $m+n−2$.
Then i am stack to finish this problem, can you help me guys ?

A: HINT: You know that a connected graph contains an Euler circuit if and only if the degree of each vertex is even and positive. Thus, $K_m\mathop{\square}K_n$ contains an Euler circuit if and only if $m+n-2$ is even and positive, which is true if and only if $m+n$ is even and greater than $2$. 


*

*Under what conditions on $m$ and $n$ is $m+n$ even?  

*What does that tell you about $mn$ modulo $4$?

