Блог пользователя LunaticPriest

Bipartite check and having a cycle of odd number of nodes
Автор LunaticPriest, история, 5 лет назад, По-английски

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?

  • Проголосовать: нравится
  • +14
  • Проголосовать: не нравится

»
5 лет назад, # |
  Проголосовать: нравится +13 Проголосовать: не нравится

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

→ Ответить