Kronecker product connected?

Question

Hi I've started looking at Kronecker products and was wondering if anyone had an intuitive explanation as to why the Kronecker product of two graphs is connected iff one(or both) contain an odd cycle. I've looked at proofs but am not really getting a proper feel of it.

Thank you

Answer 1

This all fails if the graphs aren't connected, so we assume that they both are.

Assume none of the graphs have odd cycles. Then both of them are bipartite. Let $G, H$ be the two graphs, and let $G_1, G_2$ be the bipartite partition of $G$ and $H_1, H_2$ the bipartite partition of $H$. Then let a vertex $(g, h)$ in $G\otimes H$ be called even if $g\in G_1, h\in H_1$ or $g\in G_2, h\in H_2$ and uneven otherwise. It is clear that even vertices only have even neighbours, and the same for uneven, so the product is disconnected.

Now assume that $G$ is nonbipartite (i.e. it has an odd cycle), and let $(g, h)$ and $(g', h')$ be two vertices in $G\otimes H$. Say we have a path $gg_1g_2\cdots g_ng'$ from $g$ to $g'$ in $G$ that goes at least one complete lap around an odd cycle in $G$, and a path $hh_1h_2\cdots h_mh'$ from $h$ to $h'$ in $H$.

Since we can add laps around the odd cycle as we like, we may assume that the path in $G$ is at least as long as the path in $H$, i.e. $n \geq m$. If they are equal, then $(g, h)(g_1, h_1)\cdots (g_n, h_n)(g',h')$ is a path in $G\otimes H$, and we're done. If not, there are two cases:

1. $n-m$ is even. In this case, extend the path in $H$ by going back and forth between two neighbours to get a path like $hh_1hh_1\cdots hh_1hh_1h_2\cdots h_mh'$ that has the same length as the path in $G$. Now these two paths together make a path in $G\otimes H$ between $(g, h)$ and $(g',h')$.
2. $n-m$ is odd. In this case, extend the path in $G$ by going one additional lap around the odd cycle. Now the difference in length of the path in $G$ and the path in $H$ is even, and you can apply 1. above.

There isn't really much more intuition to get, I think. The Kronecker product is such an abstract construction that you have to get into the nitty-grutty details to prove anything this basic.