Can anyone give me a hint for an algorithm to find a simple cycle of length 4 (4 edges and 4 vertices that is) in an undirected graph, given as an adjacency list? It needs to use $O(v^3)$ operations (v is the number of vertices) and I'm pretty sure that it can be done with some kind of BFS or DFS.


The algorithm only has to show that there is such a cycle, not where it is.



Cycle of length 4 in an undirected graph
Oh, and there is another way, with the BFS you mentioned. Iteratively, do a BFS from each node. By slightly modifying the BFS algorithm, you can instead of computing the distances from your source vertex to any other, remember the number of shortest paths from your source vertex to any other.


If there is a vertex at distance two which has at least 2 shortest paths to the source vertex, you have found your $C\_4$. That's $O(n^3)$.


