Some months ago, I had to solve an exercise which asked to write a function which receives an adjacency matrix and returns 1 or 0 if the graph corresponding to such matrix is colourable or not with 2 colours.. In other words, it asks to check if there are cycles with an odd number of nodes..
I failed completely that exercise (and unfortunately it was an exam) and never tried to solve it anymore.. Now, I tried again to catch some ideas but all the solutions I can find seems quite complicated... Which could be an easy algorithm to solve the problem? Can you provide me with some links/hints please?
Thanks a lot!