This is a question from the book Algebraic Graph Theory, by Godsil and Royle
Show that if $X\times X \cong Y \times Y$, then $X\cong Y$
Where $X$ and $Y$ are arbitrary undirected simple graphs.
Let $G_1$ and $G_2$ be arbitrary undirected simple graphs, the product $G_1 \times G_2$ is the graph that has vertex set $V(G_1) \times V(G_2)$, and for every $g, g' \in G_1$ and $h,h'\in G_2$, $(g,h)$ is adjacent to $(g',h')$ if and only if $g$ is adjacent to $g'$ and $h$ is adjacent to $h'$.
I feel like I should be able to prove this, but I'm stumped. Can someone provide me with a hint or a proof for this statement?
The graphs are of course assumed to be finite. I believe the result is due to László Lovász, and answered a question originally asked by Alfred Tarski. The argument applies to more general finite structures, e.g., groups. Since you said you would be satisfied with a hint, I omit some details.
Given finite graphs $X$ and $Y$, let $h(X,Y)$ be the number of homomorphisms and $i(X,Y)$ the number of injective homomorphisms from $X$ to $Y$.
Suppose $X$ and $Y$ are finite graphs with $X\times X\cong Y\times Y$. Then, for any finite graph $Z$, we have $$h(Z,X)^2=h(Z,X\times X)=h(Z,Y\times Y)=h(Z,Y)^2$$ so $h(Z,X)=h(Z,Y)$ for any finite graph $Z$.
Next, from the fact that $h(Z,X)=h(Z,Y)$ for every finite graph $Z$, it follows that $i(Z,X)=i(Z,Y)$ for every finite graph $Z$. This is the trickiest part of the argument, so I leave it as an exercise for the reader. The argument I know uses the in-and-out formula (also grandiloquently called The Principle of Inclusion and Exclusion), but there may be other and better ways.
In particular, $i(X,Y)=i(X,X)\ge1$ and $i(Y,X)=i(Y,Y)\ge1$. Finally, since the structures are finite, and since there are injective homomorphisms in both directions, those homomorphisms must be isomorphisms.
P.S. It's not true for infinite graphs. Writing $+$ for disjoint union of graphs and $\infty G$ for the disjoint union of $\aleph_0$ copies of $G$, let $$X=\infty K_{1,1}+\infty K_{2,2}+\infty K_{4,4}+\infty K_{8,8}+\cdots+\infty K_{2^n,2^n}+\cdots$$ and $$Y=\infty K_{1,1}+K_{2,2}+K_{4,4}+K_{8,8}+\cdots+K_{2^n,2^n}+\cdots.$$ Then $$Y\not\cong X\cong X\times X\cong X\times Y\cong Y\times Y\cong Y\times Y\times Y.$$