SettingLet:$$UCYLE = \mathcal \{ <G> ~:~ G \text{ is an undirected graph that contains a simple cycle}\}.$$My Solutionwe show $UCYLE \in L$ by constructing $\mathcal M$ that decides $UCYLE$ using $L$ space.$\mathcal M = $On input $<G>$ where $G = (\mathbb V, \mathbb E)$:For each $v_i \in \mathbb V$, for each $v_j \in Neighbor(v_i)$, store the current $v_i$ and $v_j$.Traverse the edge $(v_i,v_j)$ and then follow all possible paths through $G$ using DFS.If we encounter $v_k \in Neighbor(v_i) / \{v_j\}$ so that there is an edge $(v_i,v_k) \in \mathbb E$, then ACCEPT. Else REJECT.First we claim $\mathcal M$ decides $UCYLE$. First, if there exists a cycle in $G$, then it must start and end on some vertex $v_i$, step one of $\mathcal M$ tries all such $v_i$'s and therefore must find the desired vertex. Next, suppose the cycle starts at $v_i$, then there must exists a starting edge $(v_i,v_j)$ so that if we follow the cycle, we come back to $v_i$ through a different edge $(v_k,v_i)$, so we accept in step three. Since the graph is undirected, we can always come back to $v_i$ through $(v_i,v_j)$, but $\mathcal M$ does not accept this case. By construction, neither does $\mathcal M$ accept if we come upon some $v_k \in Neighbor(v_i)/\{v_j\}$ but there is no edge from $v_k$ to $v_i$.\newlineNow we show $\mathcal M \in L$. First if the vertices are labled $1,\ldots,n$ where $|\mathbb V| = n$, then it requires $log(n)$ bits to specify each $v_i$. Next note in $\mathcal M$ we only need to keep track of the current $v_i$ and $v_j$, so $\mathcal M$ is $2 log(n) = O(log ~n) \in L$.My ProblemMy problem is how do you perform DFS on the graph in $log(n)$ space. For example, in the worst case where each vertex has degree $n$, you'd have to keep a counter of which vertex you took on a particular path, which would require $n \log(n)$ space. 
Solving cycle in undirected graph in log space?
algorithms;graph theory;graphs;search problem