# Need hint for bipartiteness proof

I am given a graph $$G = (V, E)$$ with $$N$$ connected components and $$G^\prime = (V^\prime, E^\prime)$$, where for each $$v \in V$$ there is $$v_1, v_2 \in V^\prime$$ and for each $$(u, v) \in E$$ there is $$(u_1, v_2), (u_2, v_1) \in E^\prime$$.

I need to prove:

$$G^\prime \textrm{ has 2N connected components} \Leftrightarrow G \textrm{ is bipartite}$$

I don't know what technique or approach I need to use to prove this in either direction. I have a feeling I can use a direct proof for both directions. I have tried to come up with something but after an hour nothing has come up.

• Do you mean $G$ has $2N$ connected component iff $G'$ is bipartite? Commented Jun 26, 2020 at 8:53
• No, I mean $G^\prime$ has $2N$ connected components if and only if $G$ is bipartite. @PålGD Commented Jun 26, 2020 at 8:57
• So, is the point maybe that if you have an even cycle in $G$, then that becomes two cycles in $G'$, but if you have an odd cycle in $G$, then that becomes one long cycle in $G'$? You are familiar with bipartite iff no odd cycle? Commented Jun 26, 2020 at 9:03
• Yeh, I did notice that when playing with examples. But how do I formalize that idea? @PålGD Commented Jun 26, 2020 at 9:09

Let's do the case $$N = 1$$.
Suppose that $$G$$ is a connected graph, and assume first that $$G$$ is bipartite, with bipartition $$X,Y$$. Let $$X_1,X_2,Y_1,Y_2$$ be the two copies of the two parts in $$G'$$. Note first that the edges in $$G'$$ either connect $$X_1$$ to $$Y_2$$ or $$X_2$$ to $$Y_1$$, and so $$G'$$ has at least two connected components.
Conversely, any path from $$X$$ to $$Y$$ in $$G$$ gives rise to a similar path in $$G'$$ from $$X_1$$ to $$Y_2$$, implying (after a short argument) that $$X_1 \cup Y_2$$ form a connected component; and similarly for $$X_2 \cup Y_1$$. Thus $$G'$$ has exactly two connected components.
Now suppose that $$G$$ is a connected non-bipartite graph. As before, the vertices in $$X_1 \cup Y_2$$ are all in the same connected component of $$G'$$, as are the vertices in $$X_2 \cup Y_1$$. We will show that $$X_1$$ is connected by a path to $$X_2$$, implying that $$G'$$ is connected.
Since $$G$$ is not bipartite, there is some odd cycle in $$G$$. Let $$x$$ be a vertex on this odd cycle. Lifting this cycle to $$G'$$, we obtain a path from $$x_1$$ to $$x_2$$.