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

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


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Browse other questions tagged or ask your own question.