I still continue to work on complexity, for the following algorithm I would like to know:
- The space complexity
- How can we show that $G$ contains a cycle if and only if there is a point $u$ and an edge $(u,v)$ around $u$ such that the explorer leaving $u$ by the edge $(u,v)$ does not return to $u$ by $(u,v)$.
Algorithm to detect if an undirected graph $G = (V, E)$ has a cycle :
Imagine that $V = \{1 ...|V|\}$ (in other words that the vertices are numbered from $1$ to $|V|$ ). An explorer plants a flag on point $1$ and then moves on the graph according to the following principle.
- For each vertex $u \in V$ the different edges $(u,v)$ around the point $u$ can be ordered according to the size of $v$. So we can talk about the ith edge around $u$. . Note that if $(u,v)$ is the ith edge around $u$ it is possible that $(v,u)$ is not the ith edge around from $v$.
- If the explorer reaches the point $u$ of degree $k$ using the ith edge around $u$ then it starts from $u$ using the $(i + 1)$ th edge around from $u$. If $i = k$ then the explorer starts from the first edge around $u$.
As a first attempt, the explorer leaves point $1$ using the first edge around $1$. If it returns to point $1$ by a different edge then he concludes that $G$ contains a cycle.
If on the other hand it returns to point $1$ to across the same edge, then it begins its exploration again, starting by the second edge of point $1$, then the third edge and so on.
If he has exhausted all edges around $1$ and has always returned to $1$ by the same edge, so he plants his flag on point $2$ and so on.
If I am right, the algorithm is made of straight loops, and requires sorting around every vertex. But nothing mandates to store the sorting order, so the whole algorithm can be implemented in constant space $O(1)$.