How to Check if a Graph Is Bipartite

Bipartite Graphs

A graph is bipartite if its vertices can be divided into two disjoint sets U and V such that every edge connects a vertex in U to a vertex in V. Equivalently, a graph is bipartite if and only if it contains no odd-length cycles.

Two-Coloring Algorithm

Checking bipartiteness is equivalent to checking if the graph is 2-colorable:

1. Start BFS/DFS from any node, color it RED
2. Color all its neighbors BLUE
3. Color all their uncolored neighbors RED
4. If you ever find a neighbor with the same color as the current node, the graph is not bipartite
5. Repeat for each unvisited component

A(RED) → B(BLUE), C(BLUE)
B(BLUE) → D(RED)
C(BLUE) → D(RED)   ✓ Bipartite!

A(RED) → B(BLUE) → C(RED) → A(RED)?
Wait, A is already RED and C is RED, but C→A? Same color!
→ NOT bipartite (odd cycle A-B-C-A)

Time Complexity

O(V + E) — same as BFS/DFS since we visit every node and edge once.

Bipartite ↔ No Odd Cycles

This equivalence is a theorem in graph theory (König's theorem). A graph is bipartite if and only if it contains no cycle of odd length. The two-coloring algorithm implicitly detects odd cycles.

Applications of Bipartite Graphs

• Matching problems — Assigning jobs to workers, students to schools
• Scheduling — Two groups (time slots and events) with compatibility edges
• Conflict detection — If a graph is not bipartite, there are unavoidable conflicts

Maximum Bipartite Matching

Once you know a graph is bipartite, algorithms like the Hungarian algorithm or Hopcroft-Karp can find the maximum matching — the largest set of edges with no shared vertices.