# Is deciding whether or not a graph is bipartite in $L$?

Let's consider the problem:

Prove that decision whether a graph is bipartite is in $LOGSPACE$.

I am convinced that I should use Reingold's theorem. I know that I test whether graph contains an odd-length cycle.

For a given graph $G = (V,E)$ I can define the graph $$G' = (V', E') \\ V' = \{ v^1, v^2 | v \in V \} \\ E' = \{(u^1, w^2), (u^2, w^1) | (u,w) \in E\}$$

And now, the vertex $v$ resides in odd-length cycle iff there is a path between $v^1$ and $v^2$.

But, how can I construct $G'$ using $LOG$ memory?

Recall that if $A$ is logspace reducible to $B$ and $B\in L$, then $A\in L$. To decide $A$ in logspace, you don't actually compute the reduction (as its output can be of polynomial length), but compute a single bit of the reduction whenever it is requested. More concretely, suppose $f$ is a logspace reduction from $A$ to $B$. To decide $A$, given input $x$, execute the logspace machine for $B$ and keep a counter $i$ for the location on its input tape. Whenever $B$ wants to read a symbol from its input, compute the $i$'th bit of $f(x)$, which requires only logarithmic space (as $f$ is a logspace reduction from $A$ to $B$).
This show that you don't actually need to construct $G'$ entirely. You only need to compute a given bit of its adjacency matrix in logarithmic space.