Is Graph Bipartite
Recognize the pattern
Brute force idea
A straightforward first read of Is Graph Bipartite is this: 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.
Better approach
The deeper shift in Is Graph Bipartite is this: 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.
Key invariant
The truth you want to protect throughout Is Graph Bipartite is this: 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.
Watch out for
One easy way to drift off course in Is Graph Bipartite is this: 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.