4
$\begingroup$

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

$\endgroup$
  • $\begingroup$ Are your graphs finite? $\endgroup$ – Hagen von Eitzen Sep 20 at 12:03
  • $\begingroup$ No, for any graph $\endgroup$ – Farshad Hasani Sep 20 at 12:11
  • 3
    $\begingroup$ 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$. $\endgroup$ – Hagen von Eitzen Sep 20 at 16:30
  • $\begingroup$ Your counterexample is good. Thank you. So how about for finite graphs? $\endgroup$ – Farshad Hasani Sep 20 at 17:34
2
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.