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

I want to show that $$USTCON\le_L CO-2Col$$ (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.

I know this can be solved by simply using the $$USTCON$$ decision algorithm and then output a bipartite or non-bipartite graph accordingly. But is there any other reduction that actually changes the input graph?

Let USTCON2 be the following problem: given a graph $$G$$ and two vertices $$s,t$$, decide whether there is a walk from $$s$$ to $$t$$ of even length. Let us show first that USTCON2 reduces to co2COL.
Given a graph $$G = (V,E)$$ and two vertices $$s,t$$, construct a new graph whose vertex set consists of two copies of $$V$$. For every $$(a,b) \in E$$, connect $$a$$ in the first copy to $$b$$ in the second copy, and $$a$$ in the second copy to $$b$$ in the first copy. So far the graph is bipartite. Now connect $$s$$ and $$t$$ in the first copy. The new graph is bipartite iff there is no path of even length from $$s$$ to $$t$$ in the original graph.
Now let us reduce USTCON to USTCON2. Given a graph $$G = (V,E)$$ and two vertices $$s,t$$, add two new vertices $$x,y$$, and edges $$(s,x),(x,y),(y,s)$$. There is a walk from $$s$$ to $$t$$ in the original graph iff there is a walk of even length from $$s$$ to $$t$$ in the new graph.