# Detected if an undirected graph G has a cycle [duplicate]

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 :

1. 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)$$.
2. What is the is the space complexity of the algorithm described here?
• thank you for your comment, i try to follow their method but i am a little lost. But I have the impression that it is not quite the same algorithm. – tala Apr 10 at 1:07