[Math] Find an odd-length cycle in an undirected graph.

algorithmsgraph theory

I have an exam next week and I found a question that I have difficults to solve:

Given the following:

Input: Simple undirected graph $G(V, E)$.

Output: Find an odd-length cycle in $G$ or show a message that all the cycles are even-length.

Suggest an algorithm to do so.

Can you please give me some ideas to do so? Please don't give me the full answer, just a direction.

Thanks!

Best Answer

Some useful properties : http://en.wikipedia.org/wiki/Bipartite_graph#Properties

A graph is bipartite if and only if it has no odd cycle.

Also, a graph is bipartite if and only if it is 2-colorable.

The rest is up to you :)

Related Question