The following is a dublicate of the question presented here:
Let $G$ and $H$ be simple graphs. We build the graph $G\times H$ such that every vertex $(u,v) \in V(G\times H)$ is an ordered pair of one vertex from G(the first) and another from H(the latter). Additionally, two vertices $(u_1,v_1),(u_2,v_2)$ are connected if and only if $u_1$ and $u_2$ are connected in $G$, and $v_1$ and $v_2$ are connected in $H$. I need to prove that $G\times H$ is connected if and only if both graphs are connected, and at least one isn't bi-partite. Any hints / suggestions ??
As pointed out by Joffan, one of the graphs not being bi-partite is equivalent to the graph having an odd cycle. But I do not understand the rest of the proof. First of all, it is not proven that if $G \times H$ is connected then one of the graphs has an odd cycle and to be honest I have no idea how to even begin with this proof. Also, in Joffan's proof, to prove that $G \times H$ is connected, we have to prove that any 2 random verices are connected. Suppose $u_1,u_2 \in V(G)$ two random vertices where the edge $(u_1,u_2)\notin E(G)$ (but of course there exists a path $u_1 \rightarrow u_2$) and $v_1,v_2 \in V(H)$ with neither $v_1$ nor $v_2$ being a part of the odd cycle. How could we prove that there exists a path in $G \times H$ from the vertex $(u_1,v_1)$ to $(u_2,v_2)$?