Trying to understand complexity well, I found myself with the following problem.

Consider the following 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.

My questions are :

- 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)$ .
- What is the is the space complexity of the algorithm described here?