Hi everyone,

I'm struggling to come up with a correct and efficient algorithm that is able to find an odd-length cycle in an undirected graph. Any odd-length cycle is fine. I already know that a graph has an odd-length cycle if and only if it's not bipartite, but the problem is that this only tells you whether there is an odd-length cycle or not, but it doesn't find you an actual cycle in case there is one. One possible approach I came up with is to run DFS and every time there is a back-edge check if the cycle formed by the back-edge has an odd length, but the problem with this strategy is that it would only test a subset of the cycles, but not all possible cycles (think of complex cycles using many back edges in complex ways). Does any one know how to solve this problem?

Thank you guys in advance.