A graph is bipartite if you can split all its vertices into two groups so that every edge connects a vertex in one group to a vertex in the other. No edge ever connects two vertices within the same group. The most practical way to check this is by trying to two-color the graph: assign each vertex one of two colors so that no two adjacent vertices share the same color. If you can do it, the graph is bipartite. If you hit a conflict, it’s not.
What Makes a Graph Bipartite
A bipartite graph has its vertex set divided into two disjoint subsets, often called V1 and V2. Every vertex belongs to exactly one subset, and every edge in the graph goes between V1 and V2. There are no edges linking two vertices that sit in the same subset. Think of it like a matchmaking scenario: you have two groups of people, and connections only exist between groups, never within one.
A complete bipartite graph takes this to the extreme. If one group has p vertices and the other has q, a complete bipartite graph (written K_p,q) has an edge between every possible pair across the two groups. K_3,3, for example, connects each of three vertices on one side to all three on the other, giving nine edges total.
The Odd Cycle Rule
There’s a clean mathematical theorem that governs bipartiteness: a graph is bipartite if and only if it contains no odd-length cycle. A cycle is a path that starts and ends at the same vertex without repeating any edges. If every cycle in the graph has an even number of edges (4, 6, 8, …), the graph is bipartite. If even one cycle has an odd number of edges (3, 5, 7, …), it is not.
The intuition here is straightforward. Imagine walking along a cycle and alternating colors as you go: black, white, black, white. If the cycle has an even number of vertices, you arrive back at your starting vertex and the colors match up perfectly. If it has an odd number, you return to the start needing the opposite color from what you already assigned. That’s a contradiction, and it means two-coloring is impossible.
A triangle (three vertices, three edges) is the simplest odd cycle. Any graph containing a triangle cannot be bipartite. Trees, on the other hand, have no cycles at all, so every tree is automatically bipartite.
Two-Coloring by Hand
For small graphs, the fastest method is to grab two colors and try to color the graph yourself. Pick any vertex and color it, say, black. Color all its neighbors white. Then color all their uncolored neighbors black, and keep going. At each step, a vertex gets the opposite color of whichever neighbor led you to it.
If you make it through every vertex without conflict, the graph is bipartite, and the two color classes are your two vertex subsets. If you ever reach a vertex that’s already been colored and find it has the same color as the neighbor you’re coming from, the graph is not bipartite. That conflict means an odd cycle exists somewhere in the structure.
For disconnected graphs, you need to repeat this process starting from an unvisited vertex in each connected component. A graph is bipartite only if every component is individually bipartite.
Using BFS to Check Programmatically
The hand-coloring method translates directly into an algorithm using breadth-first search (BFS). This is the standard approach in computer science, and it runs in linear time relative to the number of vertices and edges.
Here’s how it works:
- Start: Pick a source vertex and assign it color 0.
- Explore neighbors: Run BFS from that vertex. Each time you discover an unvisited neighbor, assign it the opposite color of the vertex you came from (0 becomes 1, 1 becomes 0).
- Check non-discovery edges: When BFS encounters a vertex that’s already been visited, compare colors. If both endpoints of that edge share the same color, the graph is not bipartite.
- Handle components: If any vertices remain unvisited after BFS finishes, start a new BFS from one of them. Repeat until all vertices are visited.
If BFS completes without finding any same-color edge, the graph is bipartite. The coloring you produced during the search is a valid partition into two sets. You could use depth-first search (DFS) instead of BFS with the same coloring logic, and it would work identically.
A Quick Example
Consider a graph with four vertices (A, B, C, D) and edges A-B, B-C, C-D, D-A. Start at A and assign color 0. B gets color 1. C gets color 0. D gets color 1. When you check the edge D-A, D is color 1 and A is color 0. No conflict. The graph is bipartite, with {A, C} in one group and {B, D} in the other. This is just a four-vertex cycle, which has even length.
Now add edge A-C. Start at A (color 0), B gets 1, C gets 0. But A-C is an edge, and both A and C are color 0. Conflict. The graph is no longer bipartite, because the triangle A-B-C is an odd cycle.
Spotting Bipartiteness by Structure
Some graph families are always bipartite, and recognizing them can save you the work of running through the coloring process:
- Trees and forests: No cycles at all, so trivially bipartite.
- Even-length cycles: A single cycle with 4, 6, 8, or any even number of vertices is bipartite.
- Grid graphs: A rectangular grid of vertices (like a chessboard) is bipartite. The black and white squares of a chessboard are literally the two partitions.
- Any graph with no edges: Bipartite by default, since there are no edges to violate the condition.
Conversely, any graph containing a triangle or any other odd cycle is guaranteed to be non-bipartite. Complete graphs on three or more vertices (K_3, K_4, K_5, …) always contain triangles, so they’re never bipartite.
The Adjacency Matrix Approach
If you’re working with adjacency matrices, there’s a spectral property worth knowing. For a bipartite graph, the eigenvalues of the adjacency matrix are symmetric around zero: whenever some value is an eigenvalue, so is its negative. For a connected graph specifically, the graph is bipartite if and only if the largest eigenvalue equals the negative of the smallest eigenvalue.
This approach is more relevant in linear algebra or spectral graph theory contexts than in everyday algorithm design. For practical purposes, BFS-based two-coloring is simpler and faster. But if you already have the eigenvalues computed for some other reason, checking this symmetry is a quick confirmation.