LunaticPriest's blog

Bipartite check and having a cycle of odd number of nodes
By LunaticPriest, history, 5 years ago, In English

Is "checking if a graph can be colored by two colors" problem the same as "checking if a graph contains a cycle of an odd number of nodes"? Can we say that a graph is bipartite if it doesn't contain an odd cycle? Are they equivalent statements?

  • Vote: I like it
  • +14
  • Vote: I do not like it

»
5 years ago, # |
  Vote: I like it +13 Vote: I do not like it

Yes, they are equivalent.

If there is a bicoloring, then we get a contradiction by assuming there is an odd cycle (would have 2 adjacent nodes of the same color).

Given no odd cycle exists, we can give a coloring generated by the depths modulo 2 of nodes in any DFS tree. The coloring would be fine from the point of view of the back edges as well (because otherwise the back edge together with the tree path between the 2 nodes would give an odd-length cycle).

Therefore, the 2 statements are equivalent

→ Reply