Graph Theory Question (Bipartite graph/Cartesian) Prove that G and H are bipartite if any only if G x H is bipartite.
Can anyone give me an idea of how to start this proof?
 A: HINT: I’m assuming that you mean the product written $G\square H$ here. If $G$ and $H$ are bipartite, let the two parts of $V(G)$ be $A$ and $B$, and let the two parts of $V(H)$ be $C$ and $D$. Then $V(G\square H)$ is the disjoint union of the four sets $A\times C$, $A\times D$, $B\times C$, and $B\times D$. Consider a vertex $\langle a,c\rangle\in A\times C$; it’s adjacent to $\langle x,y\rangle\in V(G\square H)$ iff either $a=x$ and $y$ is adjacent to $c$ in $H$, or $c=y$ and $x$ is adjacent to $a$ in $G$. In the first case $\langle x,y\rangle\in A\times D$, and in the second case $\langle x,y\rangle\in B\times C$. If you continue this analysis, you should have no trouble splitting $V(G\square H)$ into two parts that witness bipartiteness of $G\square H$.
The other direction is perhaps a little less straightforward to approach. Assume that $G\square H$ is bipartite, and let $A$ and $B$ be the parts of $V(G\square H)$. Fix an $x_0\in V(G)$, and let $$A_H=\{y\in V(H):\langle x_0,y\rangle\in A\}$$ and $$B_H=\{y\in V(H):\langle x_0,y\rangle\in B\}\;.$$ Show that the sets $A_H$ and $B_H$ witness bipartiteness of $H$.
A: Assume $G$ and $H$ are bipartite. Each circuit in $G\Box H$ can be split into  edges coming either from $G$  or edges coming from $H$ (but not both). These edges form an even circuit in $G$ and an even circuit in $H$ (not necessarily simple). The number of edges of  the circuit in $G\Box H$ is the sum of the two circuits and therefore even.
The other direction is also straightorward. If $G\Box H$ is bipartite there are no odd circuits in $G\Box H$. Since both $G$ and $H$ are subgraphs of $G\Box H$ there are no odd circuits   in $G$ and there are no odd circuits in $H$. Hence they are bipartite. 
