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

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.

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

• A graph is bipartite iff it has no odd cycles.

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

• We can also implement a disjunction ("or") using undirected connectivity.

Here are some ideas for the other direction:

• Every graph can be made bipartite by splitting every edge into a path of length $2$.

• What happens when we join $s$ and $t$, after splitting the edges?

StackExchange Computer Science Q#7568, answer score: 4