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

Question

Prove that $K_m \mathop{\square} K_n$ contains an Eulerian circuit if and only if $mn\equiv 0,1\pmod 4 $ and both $m,n \gt 1$. anyone know to find the hint or some reference ?

Note : $K_m \mathop{\square} K_n$ it means Cartesian product of two graphs.

Answer 1

Corrected.

You’re using a different symbol for it, but I’m assuming that you mean the Cartesian graph product as defined here.

HINT: We can take the vertex set of the product graph to be $[m]\times[n]$; $\langle i,j\rangle$ is adjacent to $\langle k,\ell\rangle$ iff either

• $i=k$, and $j$ is adjacent to $\ell$, or
• $j=\ell$, and $i$ is adjacent to $k$.

Since two vertices of a complete graph are adjacent iff they are not equal, we see that $\langle i,j\rangle$ is adjacent to $\langle k,\ell\rangle$ in the product graph iff either $i=k$ and $j\ne\ell$, or $j=\ell$ and $i\ne k$. In particular, the degree of any vertex of the product graph is $(m-1)+(n-1)=m+n-2$.

• Observe that $m+n-2$ is even iff $m$ and $n$ have the same parity.

This is not equivalent to the statement that $mn\equiv 0,1\pmod 4$ and $m,n>1$: the case $K_3 \mathop{\square} K_4$ is a counterexample, since $3\cdot4=12\equiv 0\pmod 4$, but every vertex of the graph has degree $5$, so the graph has no Euler circuit. Unless some other notion of Cartesian graph product is intended, the second condition should be that $m\equiv n\pmod 2$ with $m,n>1$.