$K_m \mathop{\square} K_n$ contains an Eulerian circuit

Question

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 ?

Answer 1

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$?