Isomorphism between a cart. graph product and one of its factors implies there was only one factor

20 Views Asked by At

For simplicity assume we deal with simple undirected graphs. Let $F$ be a (possibly finite) sequence of graphs, $\alpha\subseteq\omega$ its cardinal domain and $V_F,E_F$ the respective sequence of the graphs' vertices and edges. Set $$\prod V_F = \{(v_{i\in\alpha}):v_i \in V_F(i)\}$$ as the vertices of the product graph. Two vertices $(v_{i\in\alpha}), (w_{i\in\alpha})$ are connected in the product graph iff there exists a $j\in\alpha$ such that $\{v_j,w_j\}\in E_F(j)$ and for all $i\in\alpha\setminus\{j\}$ we have $v_i=w_i$.

One can show easily that if $\alpha=1$, i.e. F is non empty trivial, then the product graph is isomorphic to its single factor. Intuition tells us on the other hand, that if the product graph is isomorphic to one of its factors, all but that one factor must be the trivial graph. But is that true?

I struggle to prove that. As soon as two graphs have the same infinite order, we cannot argue by the order anymore. Another idea is to take any non trivial graph $G$ and multiply it by itself $\omega$ times to get $G^\omega$. Then $G^\omega \times G^\omega = G^\omega$. But I'm very unsure how to prove that.