Is Graph Bipartite
Signals to notice
Brute force first
Try all 2^n colorings — exponential. That instinct is useful because it follows the prompt literally, but it usually keeps revisiting work the problem is begging you to organize.
The key insight
BFS/DFS coloring: assign color 0 to start, color 1 to neighbors, color 0 to their neighbors, etc. If any neighbor already has the same color, not bipartite. Once you hold onto the right piece of information from moment to moment, the problem feels less like trial and error and more like following a shape that was there all along.
What must stay true
A graph is bipartite if and only if it contains no odd-length cycles. BFS coloring detects this — a conflict means an odd cycle exists. If that remains true after every update, the rest of the reasoning has a stable place to stand.
Easy way to go wrong
Only checking one connected component — the graph may be disconnected. Run the coloring from every unvisited vertex. The fix is usually to return to the meaning of each move, not just the steps themselves.