The one method that was suggested was to calculated the connected components and for each component containing 3 or more vertex indices delete one edge. If after this the total number of connected components does not change there is a cycle which can be calculated by using any shortest_path alg.
Another method, if you updated to version 0.8.0 is to use get_all_simple_paths function (the output is a list of lists containing vertex indexes). If the output has 2 or more elements than there is at least one cycle (len(output)- 1 cycles, because one element will just be the actual edge between the selected vertices).
Any ideas for a better algorithm ?