I have difficulties with proving the properties of replacement product operation between two graphs. Actually, I'm not sure where to start on this proof.
- Let G and H be connected graphs. Prove that replacement product of G and H be also connected.
- Let R denote the replacement product of G and H. Prove that $\operatorname{diam}(R)≤\operatorname{diam}(G)·\operatorname{diam}(H)$.
I will be very grateful for every hint or solution.
The first problem isn’t too hard; I’ll sketch the argument and leave it to you to write it up carefully. Let $R$ be the replacement product. Because $H$ is connected, so is each cloud of $R$. Now suppose that $v_{ij}$ and $v_{k\ell}$ are vertices of $R$ in different clouds (i.e., $i\ne k$). $G$ is connected, so there is a path in $G$ from $i$ to $k$. In the simplest case this is simply an edge $\{i,k\}$ in $G$, and in that case by definition there are $j_1$ and $\ell_1$ such that $\{v_{ij_1},v_{k\ell_1}\}$ is an edge of $R$. In other words, if there is an edge between two vertices in $G$, there is an edge between their clouds in $R$. That edge connects the $i$ and $k$ clouds of $R$, and those clouds are connected, so there must be a path from $v_{ij}$ to $v_{k\ell}$. It should be clear that this idea can be extended to longer paths; perhaps the easiest way is to do it by induction on the length of the path from $v_{ij}$ to $v_{k\ell}$.
The same idea can be used in the second problem: in the worst case the shortest path from $v_{ij}$ to $v_{k\ell}$ would require $\operatorname{diam}(H)$ steps in each cloud and $\operatorname{diam}(G)$ steps between clouds.