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 :)