Proof of the number of edges in the Kronecker product of two graphs

Question

I'm wondering if somebody could point me to a proof of the fact that

$|E(G \otimes H)| = 2*|E(G)| |E(H)| $.

I found a paper that referred me to another paper, but this didn't have the proof. I think I know why it is true, but I am having trouble formulating a precise proof and a lot of places don't give a proof as it seems it's elementary.

My thinking is: think about the kronecker product of edges.For every edge in $G$ and in $H$ we get what we could think of as $4$ edges in $G \otimes H$. But every edge has two vertices so that's why the result is as above.

I'm finding it hard to formulate this into a proof as we tend to think of Kronecker products as products as vertices, not edges.

Thanks

Answer 1

I will assume that $G$ and $H$ are simple. If $u,u'\in V(G)$ and $v,v'\in V(H)$, then $\langle u,v\rangle$ is adjacent to $\langle u',v'\rangle$ in $G\otimes H$ iff $u$ and $u'$ are adjacent in $G$ and $v$ and $v'$ are adjacent in $H$. Thus, we can define a map

$$\varphi:E(G\otimes H)\to E(G)\times E(H):\{\langle u,v\rangle,\langle u',v'\rangle\}\mapsto\langle\{u,u'\},\{v,v'\}\rangle\;.$$

Suppose that $\{\langle u_0,v_0\rangle,\langle u_0',v_0'\rangle\},\{\langle u_1,v_1\rangle,\langle u_1',v_1'\rangle\}\in E(G\otimes H)$ and

$$\varphi\big(\{\langle u_0,v_0\rangle,\langle u_0',v_0'\rangle\}\big)=\varphi\big(\{\langle u_1,v_1\rangle,\langle u_1',v_1'\rangle\}\big)\;.$$

then

$$\big\langle\{u_0,u_0'\},\{v_0,v_0'\}\big\rangle=\big\langle\{u_1,u_1'\},\{v_1,v_1'\}\big\rangle\;,$$

so $\{u_0,u_0'\}=\{u_1,u_1'\}$, and $\{v_0,v_0'\}=\{v_1,v_1'\}$. Moreover, we know that $u_0\ne u_0'$, $v_0\ne v_0'$, $u_1\ne u_1'$, and $v_1\ne v_1'$. It therefore follows from $\{u_0,u_0'\}=\{u_1,u_1'\}$ that either $u_0=u_1$ and $u_0'=u_1'$, or $u_0=u_1'$ and $u_0'=u_1$. Similarly, either $v_0=v_1$ and $v_0'=v_1'$, or $v_0=v_1'$ and $v_0'=v_1$. This looks like $4$ possibilities, but let’s write them out and take a closer look.

Let $e_0=\{\langle u_0,v_0\rangle,\langle u_0',v_0'\rangle\}$ and $e_1=\{\langle u_1,v_1\rangle,\langle u_1',v_1'\rangle\}$.

• $u_0=u_1$, $u_0'=u_1'$, $v_0=v_1$, and $v_0'=v_1'$: clearly $e_0=e_1$.
• $u_0=u_1$, $u_0'=u_1'$, $v_0=v_1'$, and $v_0'=v_1$: then $e_1=\{\langle u_0,v_0'\rangle,\langle u_0',v_0\rangle\}\ne e_0$.
• $u_0=u_1'$, $u_0'=u_1$, $v_0=v_1$, and $v_0'=v_1'$: then $$e_1=\{\langle u_0',v_0\rangle,\langle u_0,v_0'\rangle\}=\{\langle u_0,v_0'\rangle,\langle u_0',v_0\rangle\}$$ just as in the previous case.
• $u_0=u_1'$, $u_0'=u_1$, $v_0=v_1'$, and $v_0'=v_1$: then $$e_1=\{\langle u_0',v_0'\rangle,\langle u_0,v_0\rangle\}=e_0\;.$$

Thus, each edge $\big\langle\{u,u'\},\{v,v'\}\big\rangle\in E(G)\times E(H)$ actually has just $2$ edges of $G\otimes H$ in its pre-image under $\varphi$, $\{\langle u,v\rangle,\langle u',v'\rangle\}$ and $\{\langle u,v'\rangle,\langle u',v\rangle\}$. The map $\varphi$ is therefore $2$-to-$1$, and it is certainly surjective, so

$$|E(G\otimes H)|=2|E(G)|\cdot|E(H)|\;.$$