# Detecting odd cycle using mod operator and breadth first search algorithm

If we want to detect and odd cycle if an undirected graph $$G=$$. Suppose we run BFS algorithm from CLRS book as follows,

Q: Now my question is suppose we have the following graphs:

The figure to the left above:

• $$d[v] \bmod{2} == d[u] \bmod{2}$$ equal and gives odd cycle.
• $$d[v] \bmod{2} == d[a] \bmod{2}$$ not equal remainder, so won't give odd cycle.

The figure to the right above:

• $$d[x] \bmod{2} == d[u] \bmod{2}$$ not equal remainder, so won't give odd cycle.
• $$d[x] \bmod{2} == d[v] \bmod{2}$$ not equal remainder, so won't give odd cycle.

Problem: so the only case to discover odd cycle is when we have the left right graph and when exactly we compare vertex $$v$$ distance with $$u$$ distance. What do you think please? If the mod operator works, can you give your interpretation as why this should work in general please if possible?

• Thank you very much. The mod operator above operates on $d[vertex]=distance$, so it assumes that there is an odd if the mod of both vertices are equal, then we have an odd cycle. So I was trying to ask if this will work for general case. So in case of an odd and 2-colorable please, how the odd cycle above would be a 2-colorable and the even cycle to right not please? Can you just give an example please?