1
$\begingroup$

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.

$\endgroup$
4
  • $\begingroup$ Do you mean $G$ has $2N$ connected component iff $G'$ is bipartite? $\endgroup$
    – Pål GD
    Commented Jun 26, 2020 at 8:53
  • $\begingroup$ No, I mean $G^\prime$ has $2N$ connected components if and only if $G$ is bipartite. @PålGD $\endgroup$
    – Tom Finet
    Commented Jun 26, 2020 at 8:57
  • $\begingroup$ 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? $\endgroup$
    – Pål GD
    Commented Jun 26, 2020 at 9:03
  • $\begingroup$ Yeh, I did notice that when playing with examples. But how do I formalize that idea? @PålGD $\endgroup$
    – Tom Finet
    Commented Jun 26, 2020 at 9:09

1 Answer 1

1
$\begingroup$

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$.

$\endgroup$

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.