Algorithms and Data Structures · Middle · Question 61 of 75
How do you check if a graph can be colored with two colors so that no edge connects equal colors?
- ✓Correct answer: BFS or DFS, giving neighbors the opposite color
- 2Count vertices: it's possible when the number is even
- 3Check that every vertex has at most two neighbors
Explanation
Such a graph is bipartite. A conflict means there's an odd cycle, and then two colors aren't enough. Typical problem: split people into two teams where rivals end up in different teams.