When is a graph which is a combination of two graphs connected Let $G$ and $H$ be simple graphs, we build the graph $G \times H$ such that every vertex $(u,v)$ in $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 ??
Thanks in advance :D 
P.s sorry for the formatting, I'll correct the mathematical notation as soon as I get home

Note that $(u_1,v_1)$ and $(u_1,v_2)$ are not connected by an edge in $G\times H$. 
The requirement that the graphs $G$ and $H$ are connected is fairly straightforward. If say G can be decomposed into two graphs $G_1$ and $G_2$ which are not connected, then clearly there will also be no connections between $G_1\times H$ and $G_2\times H$
The requirement that at least one of the graphs is not bipartite is equivalent to requiring an odd cycle. Say such a cycle exists in graph $H$ as $h_1,h_2,...h_k$. This then allows the indirect connection of the images of any two connected points in $G$, say $g_1$ and $g_2$, through the existence of the edges $(g_1, h_1)$ $\to$ $(g_2, h_2)$ $\to$ $(g_1, h_3)$ $\to$ $\ldots$ $\to$ $(g_1, h_k)$ $\to$ $(g_2, h_1)$ $\to$ $(g_1, h_2)$ $\to$ $\ldots$ $\to$ $(g_2, h_k)$. Any two points are then connected by following a path to such a cycle.  Without such a cycle the graph divides on parity distance from some reference point.
