Isomorphism and spectrum of graphs $C_{2n + 1} \times C_{2n + 1} $ and $C_{2n + 1} \square C_{2n + 1}$

Solution 1:

We can think of $C_{2n+1} \mathbin{\square} C_{2n+1}$ as a graph whose vertices are ordered pairs $(x,y) \in \mathbb Z_{2n+1}^2$, and a pair $(x,y)$ is adjacent to four other pairs: $(x+1,y)$, $(x-1,y)$, $(x,y+1)$, and $(x,y-1)$.

Similarly, we can think of $C_{2n+1} \times C_{2n+1}$ as a graph whose vertices are ordered pairs $(x,y) \in \mathbb Z_{2n+1}^2$, and a pair $(x,y)$ is adjacent to four other pairs: $(x+1,y+1)$, $(x+1,y-1)$, $(x-1,y+1)$, and $(x-1,y-1)$.

This suggests a correspondence: $C_{2n+1} \mathbin{\square} C_{2n+1}$ uses the directions $(1,0)$ and $(0,1)$ in the same way that $C_{2n+1} \times C_{2n+1}$ uses the directions $(1,1)$ and $(1,-1)$. Therefore the function $\phi : \mathbb Z_{2n+1}^2 \to \mathbb Z_{2n+1}^2$ given by $\phi(x,y) = (x+y,x-y)$ is at least locally an isomorphism from $C_{2n+1} \mathbin{\square} C_{2n+1}$ to $C_{2n+1} \times C_{2n+1}$: the four neighbors of $(x,y)$ in one graph map to the four neighbors of $\phi(x,y)$ in the other graph.