Elijah's Notes

Bipartite Graphs Properties, Proofs, and Detection Algorithm

4 min read

Purpose

This note defines bipartite graphs, proves the characterization in terms of odd cycles, and turns that proof into a linear time detection algorithm based on BFS layers.

Definition

An undirected graph is bipartite if there exists a partition of into two sets and such that every edge in has one endpoint in and the other in .

Equivalently, is bipartite when it has a proper 2-coloring: an assignment of one of two colors to each vertex such that no edge joins two vertices of the same color. The two color classes are exactly and .

flowchart LR
    subgraph V1["V1"]
        a((a))
        b((b))
    end
    subgraph V2["V2"]
        x((x))
        y((y))
        z((z))
    end
    a --- x
    a --- y
    b --- y
    b --- z

    style a fill:#e3f2fd,stroke:#1565c0
    style b fill:#e3f2fd,stroke:#1565c0
    style x fill:#fde8c8,stroke:#c80
    style y fill:#fde8c8,stroke:#c80
    style z fill:#fde8c8,stroke:#c80

Bipartite structure shows up whenever the vertices naturally split into two kinds, for example machines and jobs in scheduling, or companies and applicants in stable matching. Many problems that are hard on general graphs get easier on bipartite graphs, maximum matching being the standard example (see network flows).

Odd-Length Cycles

Lemma: If is bipartite, then it does not contain an odd-length cycle.

Proof: Fix a proper 2-coloring of . Walking around any cycle, the colors must alternate, so returning to the start vertex after steps requires to be even. An odd cycle therefore admits no proper 2-coloring, and a bipartite cannot contain one.

Lemma: Let be a connected graph, and let be the layers produced by . Then exactly one of the following holds:

  1. No edge of joins two nodes of the same layer, and is bipartite.
  2. An edge of joins two nodes of the same layer, and contains an odd cycle (and is thus not bipartite).

Proof: In case 1, every edge joins vertices in adjacent layers (BFS layers differ by at most one across an edge), so coloring even layers one color and odd layers the other gives a proper 2-coloring.

In case 2, let be an edge with , and let be the lowest common ancestor of and in the BFS tree. The tree paths from to and from to have the same length, say , because and sit in the same layer. Those two paths plus the edge form a cycle of length , which is odd.

Case 2 with : the tree paths and plus the same-layer edge form a cycle of length 5.

flowchart TD
    z((z)) --- p((p))
    z --- q((q))
    p --- x((x))
    q --- y((y))
    x -.- y

    style x fill:#f9d0d0,stroke:#c00
    style y fill:#f9d0d0,stroke:#c00

Characterization

A graph is bipartite if and only if it contains no odd-length cycle. The first lemma gives the forward direction. The second gives the converse for connected graphs, and applying it per component covers the general case, since a graph is bipartite exactly when every component is.

Algorithm

Problem: Given a graph , output true if it is bipartite, false otherwise.

Run BFS from any vertex (repeating per connected component) and record each vertex’s layer. Then scan every edge. If some edge joins two vertices in the same layer, output false. Otherwise output true, and the even/odd layers give the two sides of the partition. Correctness is exactly the lemma above, and the runtime is the BFS runtime plus an edge scan, .

from collections import deque
 
def is_bipartite(G):
    layer = {}
    for s in G:
        if s in layer:
            continue
        layer[s] = 0
        q = deque([s])
        while q:
            u = q.popleft()
            for v in G[u]:
                if v not in layer:
                    layer[v] = layer[u] + 1
                    q.append(v)
    return all(layer[u] != layer[v] for u in G for v in G[u])

Graph View