Hints — p67 Is Graph Bipartite?

Hint 1. Bipartite means you can split nodes into two groups A and B such that every edge crosses A↔B. Equivalently, you can 2-color the graph with no monochromatic edge.

Hint 2. König’s theorem: a graph is bipartite ⟺ it contains no odd-length cycle. You don’t need to find odd cycles explicitly — the coloring algorithm detects them automatically.

Hint 3. BFS from any starting node. Color the start node 0. Each neighbor gets the opposite color. Maintain color[v] ∈ {-1, 0, 1} (-1 = uncolored).

Hint 4. While exploring, if you encounter an already-colored neighbor whose color equals the current node’s color → odd cycle exists → return False.

Hint 5. Critical: iterate over ALL nodes as potential starting points (for start in range(n): if color[start] == -1: ...). The graph may be disconnected; every component must be independently bipartite.

If stuck: see solution.py.