# Graph Homomorphism

If $$X$$ and $$Y$$ be graphs, then their product $$X\times Y$$ has vertex set $$V(X)\times V(Y)$$, and $$(x,y)\sim (x', y')$$ iff $$x\sim x'$$ and $$y\sim y'$$.

Now, Show that if $$X\times X\simeq Y\times Y$$, then $$X\simeq Y$$.

Two graphs $$X$$ and $$Y$$ are isomorphic if there is a bijection, $$\varphi$$ say, from $$V(X)$$ to $$V(Y)$$ such that $$x\sim y$$ in $$X$$ iff $$\varphi(x)\sim \varphi(y)$$ in $$Y$$.

Thanks

• Are your graphs finite? – Hagen von Eitzen Sep 20 at 12:03
• No, for any graph – Farshad Hasani Sep 20 at 12:11
• We must restrict to finite graphs because there are counterexamples in the infinite case: Let $a<0$ and $V(X)=\{\,x\in\Bbb Z\mid x>a\,\}$ and edges $x\sim y\iff x,y>0$. Then $X\times X$ consists of countably infinitely many isolated vertices, namely those $(x_1,x_2)$ with $x_1\le 0\lor x_2\le 0$ and the subgraph formed by all other vertices (i.e., with $x_1,x_2>0$) does not depend on $a$. Hence $X\times X$ is the same no matter which $a<0$ we started with. But the number of isolated vertices in $X$ itself does vary with $a$. – Hagen von Eitzen Sep 20 at 16:30
• Your counterexample is good. Thank you. So how about for finite graphs? – Farshad Hasani Sep 20 at 17:34

For the finite case this is a result of Lovasz. Two facts, first if F is a fixed graph then the number of homomorphisms from $$F$$ to $$X\times X$$ is the square of the number of homomorphisms from $$F$$ to $$X$$. Second if the number of homomorphisms from $$F$$ to $$X$$ equals the number from $$F$$ to $$Y$$, then $$X$$ and $$Y$$ are isomorphic.