I was reading a paper named Decompositions of the Kronecker product of a cycle and a path into long cycles and long paths by P. K. Jha (Indian J. pure appl. Math. 23(8): 585-606, August 1992).
In one theorem I have a doubt. I am not getting how the proof of Lemma 1.3 is done. I am not getting any idea what is the need of taking a graph like $G$ here. I will be very thankful if anybody can explain that. Here is that lemma :
Theorem 1.1 of the linked paper says the following: Let $C_m$ be a cycle, $m\ge3,$ and $P_n$ a path, $n\ge2.$ Let the vertices of $C_m$ be labeled $0,1,\ldots,m-1$ and let the vertices of $P_n$ be labeled $0,1,\ldots,n-1$. Then
I think that once you understand all of these statements, the proof of Lemma 1.3 will be easier to follow.
Let's start with 1 and 5. First color the vertices of $P_n$ alternately black and white. (Say even indexed vertices black and odd ones white.) One way to think of $C_m\times P_n$ is to replace every vertex of $C_m$ with a small copy of this bicolored $P_n.$ Recall that vertex $i$ of $C_m$ is connected to vertices $i-1$ and $i+1$ of $C_m$ (with index arithmetic performed mod $m$). To construct the edge set of $C_m\times P_n,$ connect vertex $(i,j)$ to certain vertices $(i-1,k)$ and $(i+1,k).$ Which ones? Well if $j=0$ then $(i,j)=(i,0)$ gets connected to $(i-1,1)$ and $(i+1,1).$ If $j=n-1$, then $(i,j)=(i,n-1)$ gets connected to $(i-1,n-2)$ and $(i+1,n-2).$ If $j\ne0,n-1,$ then $(i,j)$ gets connected to four vertices: $(i-1,j-1),$ $(i-1,j+1),$ $(i+1,j-1),$ and $(i+1,j+1).$ This proves 5. Also note that black vertices always get connected to white vertices and vice versa. This proves 1.
At this point, you should draw some small examples, say with $m=3$ or $4$ and $n=2$ or $3.$
Observe that if $m$ is even, then all edges as described above join vertices $(p,q)$ and $(r,s)$ in which $p+q$ and $r+s$ have the same parity. For example, $(i,0)$ gets connected to $(i-1,1)$ and $(i+1,1).$ The relevant sums are $i+0=i,$ $i-1+1=i,$ and $i+1+1=i+2,$ which all have the same parity.
The reason this is not true for $m$ odd is that if $i=m-1$, then when you connect $(i,j)=(m-1,j)$ to $(i+1,j\pm1)=(0,j\pm1),$ you are connecting vertices of opposite parity: $m-1+j$ and $0+j-1$ have odd difference, as have $m-1+j$ and $0+j+1.$ (Recall that $i+1=0$ when $i=m-1$ because index arithmetic in $C_m$ is done mod $m.$)
The observation above establishes that $C_m\times P_n$ is disconnected when $m$ is even, since there is no way to get from a vertex of one parity to a vertex of the opposite parity.
Here's another way to think about it: observe that if you follow any path in $C_m\times P_n,$ then the vertices you visit will alternate in color: black, white, black, white... Now follow a path that goes "once around", say $(0,a)$ to $(1,b)$ to $(2,c),\ldots$ to $(m-1,y)$ to $(0,z).$ If $(0,a)$ is a black vertex, then when you get back to $0$ again, $(0,z)$ will again be black if $m$ is even, but will be white if $m$ is odd. This should help you to see why $m$ even and $m$ odd are different.
We haven't said why $C_m\times P_n$ is connected for $m$ odd. This isn't hard to see. To get from $(0,0)$ to $(0,j)$ you can, if $j$ is even, follow the path $((0,0),(1,1),(0,2),(1,3),(0,4),\ldots,(1,j-1),(0,j)).$ If $j$ is odd, you can follow a similar path from $(0,0)$ to $(0,j-1).$ Then go "once around" via the path $((0,j-1),(1,j),(2,j-1),\ldots,(m-1,j-1),(0,j)).$ To get from $(0,0)$ to $(i,j),$ you can, if $i$ is even, go from $(0,0)$ to $(0,j).$ Then follow the path $((0,j),(1,j\pm1),(2,j),(3,j\pm1),\ldots,(i,j)).$ If $i$ is odd, go from $(0,0)$ to $(0,j-1).$ Then follow the path $((0,j-1),(1,j),(2,j-1),\ldots,(i-1,j-1),(i,j)).$
I'm out of steam, so I'll let you think about how to prove, for $m$ even, that there is always a path from $(0,0)$ to $(i,j)$ if $i+j$ is even, and that there is always a path from $(1,0)$ to $(i,j)$ if $i+j$ is odd. (This should be easier, since you won't need to use "once-around" paths.) I'll also let you think about how to prove that the component containing $(0,0)$ is isomorphic to the component containing $(1,0).$ If you have any questions, or need for clarification, please let me know.