Skip to main content

Coloring of subgraphs of G^n

Let $G=(L,R,E)$ be a finite bipartite graph, such that for each $v\in L\cup R: deg(v)>0$. Define $E^{(n)}=\{(\overline{l},\overline{r}) | \overline{l}=(l_1,...,l_n)\in L^n , \overline{r}=(r_1,...,r_n) \in R^n$ and for each $ 1 \le i \le n : (l_i,r_i)\in E\},$ and $G^{(n)}=(L^n,R^n,E^{(n)}).$

I want to show that for any number of colors $c>0$ exists an $n\in\mathbb{N}$ such that $G^{(n)} \mapsto (G)^2 _c $.

I thought about counting all the full sub-graphs of $G^{(n)}$ which are isomorphic to $G$ and then showing that there must be at least one full sub-graph whose edges are single colored, but I got a bit tangled doing so, which made me think there should be an easier way to do so. Am I on the right path or is there actually a more convenient way to prove this?