Module 19 · Graph Traversal and Connected Components

187. Bipartite Graph Check

Bridge · Download this solution · All solutions and shared helpers

Problem

Return whether an undirected graph can be colored with two colors such that every edge joins opposite colors. Process every component, including isolated vertices. A self-loop makes the answer false; the empty graph is bipartite.

Examples

Example 1

is_bipartite([[1,3],[0,2],[1,3],[0,2]])
=> True

The even cycle supports alternating colors.

Example 2

is_bipartite([[1,2],[0,2],[0,1]])
=> False

The odd cycle forces equal colors across one edge.

Example 3

is_bipartite([])
=> True

There is no contradictory edge.

Reveal the worked solution and reasoning

Why this mechanism works

Choose either color for an unseen component root. Every edge then forces its neighbor to the opposite color. A conflict occurs when an edge joins two vertices already assigned the same color. Disconnected components can choose their starting colors independently.

State and boundaries

color[v] is -1 if undiscovered, otherwise 0 or 1. Every processed edge has been checked for opposite endpoint colors.

Protocol

Scan all component starts.
Assign color zero to an unseen start.
Traverse its edges.
Color each unseen neighbor oppositely and schedule it.
Reject any same-color edge.
Accept after all components.

Visualization

square: 0(A)-1(B)-2(A)-3(B)-0(A) -> valid
triangle: 0(A)-1(B)-2(A)-0(A) -> conflict

Python implementation

def is_bipartite(adj):
    color = [-1] * len(adj)
    for start in range(len(adj)):
        if color[start] != -1:
            continue
        color[start] = 0
        stack = [start]
        while stack:
            u = stack.pop()
            for v in adj[u]:
                if color[v] == -1:
                    color[v] = 1 - color[u]
                    stack.append(v)
                elif color[v] == color[u]:
                    return False
    return True

Worked execution

Recorded state changes after statements; L numbers refer to the solution file. Long traces are explicitly condensed.

is_bipartite([[1,3],[0,2],[1,3],[0,2]])

L2 is_bipartite: color = [-1] * len(adj)
adj=[[1, 3], [0, 2], [1, 3], [0, 2]]; color=[-1, -1, -1, -1]

L3 is_bipartite: for start in range(len(adj)):
adj=[[1, 3], [0, 2], [1, 3], [0, 2]]; color=[-1, -1, -1, -1]; start=0

L6 is_bipartite: color[start] = 0
adj=[[1, 3], [0, 2], [1, 3], [0, 2]]; color=[0, -1, -1, -1]; start=0

L7 is_bipartite: stack = [start]
adj=[[1, 3], [0, 2], [1, 3], [0, 2]]; color=[0, -1, -1, -1]; start=0; stack=[0]

L9 is_bipartite: u = stack.pop()
adj=[[1, 3], [0, 2], [1, 3], [0, 2]]; color=[0, -1, -1, -1]; start=0; stack=[]; u=0

L10 is_bipartite: for v in adj[u]:
adj=[[1, 3], [0, 2], [1, 3], [0, 2]]; color=[0, -1, -1, -1]; start=0; stack=[]; u=0; v=1

L12 is_bipartite: color[v] = 1 - color[u]
adj=[[1, 3], [0, 2], [1, 3], [0, 2]]; color=[0, 1, -1, -1]; start=0; stack=[]; u=0; v=1

L13 is_bipartite: stack.append(v)
adj=[[1, 3], [0, 2], [1, 3], [0, 2]]; color=[0, 1, -1, -1]; start=0; stack=[1]; u=0; v=1

... 13 intermediate state changes omitted ...

L10 is_bipartite: for v in adj[u]:
adj=[[1, 3], [0, 2], [1, 3], [0, 2]]; color=[0, 1, 0, 1]; start=0; stack=[]; u=1; v=2

L3 is_bipartite: for start in range(len(adj)):
adj=[[1, 3], [0, 2], [1, 3], [0, 2]]; color=[0, 1, 0, 1]; start=1; stack=[]; u=1; v=2

L3 is_bipartite: for start in range(len(adj)):
adj=[[1, 3], [0, 2], [1, 3], [0, 2]]; color=[0, 1, 0, 1]; start=2; stack=[]; u=1; v=2

L3 is_bipartite: for start in range(len(adj)):
adj=[[1, 3], [0, 2], [1, 3], [0, 2]]; color=[0, 1, 0, 1]; start=3; stack=[]; u=1; v=2

Result: True. The even cycle supports alternating colors.

is_bipartite([[1,2],[0,2],[0,1]])

L2 is_bipartite: color = [-1] * len(adj)
adj=[[1, 2], [0, 2], [0, 1]]; color=[-1, -1, -1]

L3 is_bipartite: for start in range(len(adj)):
adj=[[1, 2], [0, 2], [0, 1]]; color=[-1, -1, -1]; start=0

L6 is_bipartite: color[start] = 0
adj=[[1, 2], [0, 2], [0, 1]]; color=[0, -1, -1]; start=0

L7 is_bipartite: stack = [start]
adj=[[1, 2], [0, 2], [0, 1]]; color=[0, -1, -1]; start=0; stack=[0]

L9 is_bipartite: u = stack.pop()
adj=[[1, 2], [0, 2], [0, 1]]; color=[0, -1, -1]; start=0; stack=[]; u=0

L10 is_bipartite: for v in adj[u]:
adj=[[1, 2], [0, 2], [0, 1]]; color=[0, -1, -1]; start=0; stack=[]; u=0; v=1

L12 is_bipartite: color[v] = 1 - color[u]
adj=[[1, 2], [0, 2], [0, 1]]; color=[0, 1, -1]; start=0; stack=[]; u=0; v=1

L13 is_bipartite: stack.append(v)
adj=[[1, 2], [0, 2], [0, 1]]; color=[0, 1, -1]; start=0; stack=[1]; u=0; v=1

... 2 intermediate state changes omitted ...

L13 is_bipartite: stack.append(v)
adj=[[1, 2], [0, 2], [0, 1]]; color=[0, 1, 1]; start=0; stack=[1, 2]; u=0; v=2

L9 is_bipartite: u = stack.pop()
adj=[[1, 2], [0, 2], [0, 1]]; color=[0, 1, 1]; start=0; stack=[1]; u=2; v=2

L10 is_bipartite: for v in adj[u]:
adj=[[1, 2], [0, 2], [0, 1]]; color=[0, 1, 1]; start=0; stack=[1]; u=2; v=0

L10 is_bipartite: for v in adj[u]:
adj=[[1, 2], [0, 2], [0, 1]]; color=[0, 1, 1]; start=0; stack=[1]; u=2; v=1

Result: False. The odd cycle forces equal colors across one edge.

Why the solution is correct

The algorithm assigns colors consistent with every traversed edge unless it detects a conflict. If none exists, the assignments themselves witness bipartiteness. A conflict corresponds to incompatible parity requirements along discovered paths, so no two-coloring can satisfy that component.

Time and space

O(V+E) time and O(V) auxiliary color/frontier space.

Common mistakes

Starting from only vertex zero misses an odd cycle elsewhere. Marking a vertex without storing its required color loses the property being checked.

Reasoning card

State: color[v] is -1 if undiscovered, otherwise 0 or 1. Every processed edge has been checked for opposite endpoint colors.

Invariant: Every processed edge connects opposite colours.

Decision to rehearse: Assign opposite colour when discovering neighbours.

Finish: Accept after all components

Transfer exercise

Return an odd-cycle witness when a conflict is found by retaining traversal parents and depths.