Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

If $G= (V(G), E(G))$ and $H=(V(H), E(H))$ are graphs.

Consider the set $\mathfrak{R}(G,H)$ of "Random Cartesian Product" whose member are graphs $K =(V(K), E(K))$ defined as follow:

$$V(K) = V(G) \times V(H)\;,$$ and if $uv \in E(G)$ and $xy \in E(H)$ then either

$$\{(u,x)(v, x), (u,y)(v,y)\} \subset E(K)\;,$$


$$\{(u,x)(u,y), (v,x)(v,y)\} \subset E(K)\;,$$

but not both.

  1. Is it true that if $K \in \mathfrak{R}(G,H)$, then $K$ either contains a copy of $G$ or a copy of $H$?

  2. If $\chi(G)$, $\chi(H)$ $\gt k$, what could be said about $\chi(K)$ when $K \in \mathfrak{R}(G,H)$?

share|cite|improve this question
Please mention, and provide a link, when crossposting from another site (in this case MathOverflow). – Zev Chonoles May 26 '12 at 7:02
This is the first time I post here. Thanks for the reminder. – hbm May 26 '12 at 7:18
Have you tried proving these in specific cases? Where did you get stuck? As a matter of fact, have you any thoughts on the problem other than its bare statement? – Did May 26 '12 at 7:20
@hbm: This is a nice construction and will keep me busy investigating it! I have only just found it (1/6/12) Thanks for an interesting construction. Sorry I do not have a contentful answer at this stage. There are lots of unanswered questions under the graph thoery tag. Best Regards Herman :-) – Herman Jun 1 '12 at 15:21

We prove the first item by induction on $n=|E(G)|$ the number of edges in $G$.

$n=0$: trivial.

$n=1$: $E(G)=\{(u,v)\}$. Let $K\in\mathfrak{R}(G,H)$. Two cases:

  • either $\forall (x,y)\in E(H)$ $\{((u,x)(u,y)), ((v,x)(v,y))\} \subset E(K)$ then $K$ contain a copy of $H$.

  • or, $\exists (x,y)\in E(H)$ $\{((u,x)(v,x)), ((u,y)(v,y))\} \subset E(K)$ then $K$ contain a copy of $H$.

$n\to n+1$: Suppose the property true for all graphs such that $|E(G)|=n$. Let $G$ be a graph with $|E(G)|=n+1$, let $K\in\mathfrak{R}(G,H)$. Let $E'$ be such that $E(G)=E'(G)\cup\{(u',v')\}$ and $|E'(G)|=n$, let $G'=(V(G),E'(G))$. We define $K'$ as the sub graph of $K$ where we removed all the edges $((u',x),(v',x))$. It's easy to see that $K'\in\mathfrak{R}(G',H)$.

By induction hypothesis either $K'$ contains a copy of $H$, and since $K'$ is contained in $K$, $K$ also contains a copy of $H$. Or, $K'$ contains a copy of $G'$. Let $x'\in V(G)$ be the element shared by all the nodes of this copy. Two cases:

  • either, $((u',x'),(v',x,))\in V(K)$ then there is a copy of $G$ in $K$.
  • or, $((u',x'),(v',x,))\notin V(K)$. By definition of $K$ that mean $\forall (x,y)\in E(H), \{((u',x),(u',y)),((v',x),(v',y))\}\subset E(K)$ that means there is a copy of $H$ in $K$.

Hence in all cases there is either a copy of $H$ or a copy of $G$ in $K$.

For the second item, by using the first item we know that $\chi(K)\geq\chi(H)$ or $\chi(K)\geq\chi(G)$ hence $\chi(K)\geq k$.

share|cite|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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