# The conjuction of two graphs is connected iff one of them has an odd cycle

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)$$?

• Have you tried to compute $K_3 \times K_3$ manually? Apr 10, 2023 at 14:31
• Found the answer in mathematics stack exchange here Apr 10, 2023 at 14:39