# deciding if a graph is "colourable" with 2 colours

This is a discussion on deciding if a graph is "colourable" with 2 colours within the C Programming forums, part of the General Programming Boards category; Hello there! Some months ago, I had to solve an exercise which asked to write a function which receives an ...

1. ## deciding if a graph is "colourable" with 2 colours

Hello there!
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!
Bye!

2. If you know what the words "adjacency matrix" and "cycle" and "odd" mean, then you should be home free. (Hint: If you look at the five-step cycles (for instance) from node N to node N, how would you find how many there are using the adjacency matrix?)

3. Originally Posted by tabstop
If you know what the words "adjacency matrix" and "cycle" and "odd" mean, then you should be home free. (Hint: If you look at the five-step cycles (for instance) from node N to node N, how would you find how many there are using the adjacency matrix?)
mhmm..