Log-Space Reduction $CO-2Col \le_L USTCON$

I want to show that $CO-2Col \le_L USTCON$ (Log-Space reduction)

$USTCON$


The $s-t$ connectivity problem for undirected graphs is
called $USTCON$.


[Input]: An undirected graph $G=(V,E)$, $s,t \in V$.


[Output]: 1 iff $s$ is connected to $t$ in $G$.

$CO-2Col$


A graph is $2$-colorable if there is a way to color the vertices
of $G$ with $2$ colors, such that for every edge the two vertices
on the edge are colored differently. $CO-2Col$ is the following
problem:


[Input]: An undirected graph $G$.


[Output]: 1 iff $G$ is NOT $2$-colorable.

My solution is for an input graph $G$ the reduction outputs $(G',s,t)$ where
$s$ an arbitrary vertex of $G$, $t$ is one of its neighbours and
$G'=G^2$ namely an edge $(u,v)\in E(G')$,iff there is $w \in V (w \ne u,v)$
such that $(u,w)\in E(G)$ and $(w,v)\in E(G)$.

$G$ is bipartite
iff $G'$ is not connected (and $s$ and $t$ belongs to different
parts).

But this only works when the input graph $G$ is connected.

A counter example: (if we choose s,t to be A,B)

How can I improve my reduction that it will work at the unconnected case? or maybe a new reduction is needed?

Thanks!

Hint: Extend the input graph to a connected graph which is bipartite iff the original graph is bipartite.

If the original graph is not bipartite, then the new graph will a fortiori not be bipartite. The more difficult direction is ensuring that when the original is bipartite, the new edges do not render it non-bipartite. This property is satisfied as long as the edges that you introduce do not close an odd cycle.

Further hint: Take $n$ copies of your original graph (where $n$ is the number of vertices), and add a new vertex $s$. Connect $s$ to the $i$th vertex in the $i$th copy.

StackExchange Computer Science Q#22826, answer score: 3