In an undirected (and unweighted) graph, to find the shortest cycle containing a specific vertex $ s$ , it is usually said to run a BFS from $ s$ and the first time to find a re-visit, then that is the wanted smallest cycle length.

This does not seem to be true, quoting from https://www.cs.princeton.edu/courses/archive/spr08/cos226/exams/fin-f05-sol.pdf page 3:

Note that if you run BFS from $ s$ and stop as soon as you revisit a vertex (using a previously ununused edge), you may not get the shortest path containing $ s$ .

Examples where this technique seems to be suggested: An efficient algorithm to find a shortest cycle including a specific vertex

Another technique, finding the shortest cycle in the whole graph, by running BFS from each vertex, also seems to detect only the shortestLength + 1 in a special case, as mentioned in this paper: https://link.springer.com/chapter/10.1007/978-3-540-78773-0_63 in the “Unweighted case”. **On the contrary**, here (http://theory.stanford.edu/~virgi/cs267/lecture3.pdf) it is mentioned (first and second paragraphs) that running BFS from every vertex gives the shortest length (girth) in all cases. This is also mentioned in an archive (http://web.archive.org/web/20140513212046/https://webcourse.cs.technion.ac.il/234247/Winter2003-2004/ho/WCFiles/Girth.pdf).

Which of all algorithms/methods is true for:

- Finding the shortest-length cycle in an undirected graph?
- Finding the shortest-length cycle that passes through a known vertex $ s$ in an undirected graph?
- Where is the pitfall in each of my above compare-and-contrasts? (I cannot believe that some of the above quoted might even be untrue…)

Note: A randomized sub-cubic algorithm seems to exist, in the paper “A shortest cycle for each vertex of a graph” by Raphael Yuster: http://research.haifa.ac.il/~raphy/papers/all-cycles.pdf