Bipartite Problem is Log-Space Reducible To $s$-$t$ Undirected Connectivity

Question

Prove that the problem of determining if graph is bipartite is computationally equivalent under log-space reductions to $s$-$t$ undirected connectivity.

Problem of $s$-$t$ undirected connectivity is the following given an undirected graph $G = (V, E)$ and two designated vertices, $s$ and $t$, determine whether there is a path from $s$ to $t$ in $G$.

I assume the idea is to consider mapping from graph $G$ to bipartite graph $G'$, there should be a correspondence between edges of $G$ and edges of bipartite graph $G'$, and between edges of $G$ and the edges that violates the bipartite property of graph $G'$. The problem is I cannot come up with such correspondence.

I would appreciate any idea.

Answer 1

Here are some ideas on how to reduce checking bipartiteness to undirected non-connectivity:

1. A graph is bipartite iff it has no odd cycles.
2. Suppose we guess that vertex $v$ participates in a cycle of length $2k+1$. Using a layered graph, we can check whether it is the case using undirected connectivity.
3. We can also implement a disjunction ("or") using undirected connectivity.

Here are some ideas for the other direction:

1. Every graph can be made bipartite by splitting every edge into a path of length $2$.
2. What happens when we join $s$ and $t$, after splitting the edges?