Finding the shortest cycle containing a vertex in a graph

Given a connected undirected graph with edges $$E$$ and verticies $$V$$ and a vertex $$v \in V$$, find the length of the shortest cycle containing $$v$$. The best I could do is $$O(|E|*deg(v))$$, by trying to choose every edge connected to $$v$$ as the last edge of the cycle (you just remove that edge $$(u, v)$$, run BFS from $$v$$, and the shortest cycle ending with that edge is of length $$dist(u, v) + 1$$). How could you solve this problem in $$O(E)$$?

• Could you share more about the background in which you want this question answered? With such a broad settings, people might wonder if this is merely a homework assignment, for which cstheory.stackexchange is not the right venue (see cstheory.stackexchange.com/tour for suggestions of other venues more appropriate for such questions) May 5, 2023 at 10:49

Ok, seems the problem is actually pretty easy. Just make the BFS tree (or shortest path tree in case of a weighted graph) rooted at $$v$$, and then for every edge $$(a, b)$$ not in the tree, if $$lca(a, b)=v$$, consider it as the shortest cycle (its length being, of course, $$dist(v, a) + dist(v, b) + 1$$).