An odd cycle. Each edge imposes an opposite-color constraint; a contradiction exactly exposes an odd cycle.

Color is a parity label: how many edge flips from the component start, modulo two. Two routes with conflicting parity prove an odd cycle.

What the function promises: Return a valid list of colors 0/1, or None. Graph adjacency is undirected and labels are 0..n−1.

from collections import deque

def bipartite_colors(graph):
    color = [-1] * len(graph)
    for start in range(len(graph)):
        if color[start] != -1:
            continue
        color[start] = 0
        queue = deque([start])
        while queue:
            u = queue.popleft()
            for v in graph[u]:
                if color[v] == -1:
                    color[v] = color[u] ^ 1
                    queue.append(v)
                elif color[v] == color[u]:
                    return None
    return color

colors = bipartite_colors([[1],[0,2],[1]])
assert colors and all(colors[u] != colors[v] for u in range(3) for v in [[1],[0,2],[1]][u])
assert bipartite_colors([[1,2],[0,2],[0,1]]) is None

Work and storage: O(V+E) time and O(V) space.

When to recognize it: Each edge imposes an opposite-color constraint; a contradiction exactly exposes an odd cycle.

Check before applying it: Checking only one connected component can miss a contradiction elsewhere.

Union-find with parity can maintain relative colors, but deletions require offline or dynamic techniques.