I have this homework:
We consider the following binary operation on graphs:
if Gi = (Vi, Ei) are two graphs with |Gi| > 2 (i = 1, 2),then G1*G2 is the following graph:
V (G1*G2) = V (G1) × V (G2) and E(G1*G2) = {(u1, u2)(v1, v2) : u1v1 ∈ E(G1),u2v2 ∈ E(G2)}.
The graphs G1 and G2 have at least 2 vertices each.
Prove that G1*G2 is connected if and only if G1 and G2 are connected and one of them contains an odd circuit.
Now we have to prove "=>" and "<="
For "<="
if G1 and G2 are connected and one of them contains an odd circuit then G1*G2 is connected becouse it is complementar of (G1 U G2).
For "=>"
In this case we know that our G1*G2 is connected .Complementar of G1*G2 have 2 connected components.
Do I understand something wrong? Can anyone help me with the demonstration?
I appreciate any indication.