# Better algorithm for determining if a vertex is on any cycle in a graph

The problem I'm facing is the following:

Given a simple undirected graph $G=(V,E)$ and a vertex $u \in V$, answer if $u$ is part of any cycle of $G$.

The algorithm I can think of is to remove an edge from $u$ to one of its neighbours $v$ at a time and ask if there is still a path from $u$ to $v$ in the resulting graph, placing $(u,v)$ back before the next iteration.

I estimate the time complexity as $O(\Delta\cdot(m+n))$, with $\Delta$ being the greatest degree of the graph and $(m+n)$ for using a BFS on each iterarion.

Is there a better algorithm than this one? Does a simple DFS solve this problem and I'm just losing time with this?

DFS: Depth-First Seatch

• I searched the site for an answer to this question, but couldn't find one (maybe the terms I used in the search weren't good...) May 22, 2015 at 17:51
• When a vertex is on a cycle, it has two distinct neighbours on the same cycle (unless edges are not defined as pairs of vertices). May 22, 2015 at 23:22
• See this answer on Stack Overflow. May 23, 2015 at 6:13

You can remove the vertex $u$ and all its edges, keeping a list of its neighbours.
Properly organized, this will explore every vertex and edge at most once. (same complexity, but without $\Delta$ repetition factor).