Bipartite Graph Check

Bipartite Graph Check asks a simple-sounding question: can you split a graph's vertices into two groups so that every edge crosses between the groups? It is the graph version of a two-coloring puzzle, and BFS solves it in one sweep.

The slow way first

You might try to guess a partition and check it: assign each vertex to one of two groups, then verify no edge stays inside a group. But there are 2^n ways to assign colors — trying them all is exponential and hopeless for anything but a tiny graph.

The question to ask: do I really have a choice once I pick a starting color? No. Once vertex 0 is red, all its neighbors are forced to be blue, their neighbors forced back to red, and so on. The coloring propagates with no guesswork — which is exactly what a traversal does.

The idea: color as you traverse

Run BFS from an uncolored vertex. Give it color 0. Every time you pop a vertex u and look at a neighbor v:

• if v is uncolored, paint it the opposite color (1 - color[u]) and enqueue it;
• if v is already colored the same as u, you have found an edge inside one group — the graph is not bipartite, return False.

If BFS finishes with no such clash, the two-coloring worked. (Loop over all start vertices so disconnected pieces are covered.)

The key insight: the color of every vertex is determined the moment its first neighbor is colored. We are not searching — we are propagating a forced choice and watching for a contradiction.

Walk through it

Step through the animation. Vertex 0 starts red. BFS colors 1 and 3 blue, then 2 and 4 red, then 5 blue. Each edge lights up as it is processed. Every edge connects a red to a blue, no clash ever appears, so the verdict is bipartite = True.

Pseudocode

color = empty map (vertex -> 0 or 1)
for each start vertex with no color yet:
    color[start] = 0
    queue = [start]
    while queue is not empty:
        u = pop front of queue
        for each neighbor v of u:
            if v has no color:
                color[v] = 1 - color[u]      # opposite color
                add v to queue
            else if color[v] == color[u]:
                return False                 # same-color edge -> not bipartite
return True

The Python solution

def is_bipartite(graph):
    color = {}
    for start in range(len(graph)):
        if start in color:
            continue
        color[start] = 0
        queue = [start]
        while queue:
            u = queue.pop(0)
            for v in graph[u]:
                if v not in color:
                    color[v] = 1 - color[u]
                    queue.append(v)
                elif color[v] == color[u]:
                    return False
    return True

• color maps each vertex to 0 or 1; an absent key means uncolored.
• The outer for start loop restarts BFS on any vertex not yet reached, so disconnected components are all checked.
• queue.pop(0) takes the front of the queue — standard BFS order.
• Line 12 is the propagation: a fresh neighbor gets 1 - color[u], the opposite color.
• Lines 14-15 are the failure test — an already-colored neighbor sharing u's color is an edge inside one group, so the graph cannot be bipartite.

Complexity

We touch every vertex and every edge a constant number of times, so the traversal is linear in the size of the graph. The extra space is the color map plus the BFS queue, both O(V).

When this pattern shows up

Practice