Bipartiteness
Every Tree is Bipartite. Most Graphs Aren't.
You already know trees have no cycles. That single fact guarantees something powerful: you can always split a tree's nodes into two groups where every edge crosses between groups. No exceptions.
Add one wrong edge to a tree and that guarantee can break. The question is: which extra edges break it, and how do you detect them fast?
The answer comes down to parity. Odd cycles kill bipartiteness. Even cycles don't. And a single BFS finds out.
What Bipartite Means
A graph is bipartite if you can assign every node one of two colors --- say 0 and 1 --- such that no edge connects two nodes of the same color.
Left graph: color nodes {1, 4} as 0 and {2, 3} as 1. Every edge crosses colors. Right graph: the triangle 1-2-3 makes 2-coloring impossible. Try it --- one of the three edges will always connect same-colored nodes.
Key insight. A graph is bipartite if and only if it contains no odd-length cycle. This is a theorem, not a heuristic. One direction: if an odd cycle exists, 2-coloring fails (pigeonhole on the cycle). Other direction: if no odd cycle exists, BFS layering produces a valid 2-coloring.
The Algorithm: BFS with 2-Coloring
The approach is clean. Start from any uncolored node. Assign it color 0. BFS outward. Every neighbor gets the opposite color. If you ever find a neighbor that's already colored the same as the current node --- the graph is not bipartite.
Trace on a Bipartite Graph
| Step | Dequeue | Process neighbor | Action |
|---|---|---|---|
| 1 | --- | 1 | Assign color[1] = 0, push 1 |
| 2 | 1 | 2 | Uncolored, assign color[2] = 1, push 2 |
| 3 | 1 | 4 | Uncolored, assign color[4] = 1, push 4 |
| 4 | 2 | 1 | Already colored 0 ≠ 1. OK |
| 5 | 2 | 3 | Uncolored, assign color[3] = 0, push 3 |
| 6 | 4 | 1 | Already colored 0 ≠ 1. OK |
| 7 | 4 | 3 | Already colored 0 ≠ 1. OK |
| 8 | 3 | 2 | Already colored 1 ≠ 0. OK |
| 9 | 3 | 4 | Already colored 1 ≠ 0. OK |
Result: bipartite. Group 0 = {1, 3}, Group 1 = {2, 4}.
Trace on a Non-Bipartite Graph
Edges: 1-2, 1-3, 2-3, 2-4, 3-4.
| Step | Dequeue | Process neighbor | Action |
|---|---|---|---|
| 1 | --- | 1 | Assign color[1] = 0, push 1 |
| 2 | 1 | 2 | Uncolored, assign color[2] = 1, push 2 |
| 3 | 1 | 3 | Uncolored, assign color[3] = 1, push 3 |
| 4 | 2 | 1 | Already colored 0 ≠ 1. OK |
| 5 | 2 | 3 | Already colored 1 == 1. CONFLICT! |
Conflict at edge 2-3. Both are color 1. The triangle 1-2-3 is an odd cycle (length 3). Not bipartite.
The Code
int main() {
int n, m;
cin >> n >> m;
vector<vector<int>> adj(n + 1);
for (int i = 0; i < m; i++) {
int u, v;
cin >> u >> v;
adj[u].push_back(v);
adj[v].push_back(u);
}
vector<int> color(n + 1, -1);
bool bipartite = true;
for (int s = 1; s <= n; s++) {
if (color[s] != -1) continue;
color[s] = 0;
queue<int> q;
q.push(s);
while (!q.empty()) {
int u = q.front(); q.pop();
for (int v : adj[u]) {
if (color[v] == -1) {
color[v] = 1 - color[u];
q.push(v);
} else if (color[v] == color[u]) {
bipartite = false;
}
}
}
}
if (bipartite) {
cout << 1 << "\n";
for (int i = 1; i <= n; i++) cout << color[i] + 1 << " \n"[i == n];
} else {
cout << "IMPOSSIBLE\n";
}
return 0;
}
Complexity: \(O(n + m)\) time and space. Every node is enqueued once. Every edge is checked twice (once from each endpoint).
Why Trees Are Always Bipartite
A tree on \(n\) nodes has exactly \(n - 1\) edges and no cycles. Since bipartiteness fails only when an odd cycle exists, and trees have zero cycles, every tree is bipartite.
The 2-coloring of a tree is just "color by depth parity." Root gets color 0. Its children get color 1. Their children get color 0. And so on. BFS on a tree produces exactly this layering.
Gotcha. Don't confuse "no odd cycles" with "no cycles." A graph with only even-length cycles is still bipartite. The cycle 1-2-3-4-1 has length 4 (even), and the graph is bipartite: {1,3} vs {2,4}. Only odd cycles break things.
Disconnected Graphs
The graph might not be connected. A single BFS from node 1 won't visit nodes in other components.
The fix: loop over all nodes. If a node is still uncolored, start a new BFS from it. Each connected component is checked independently.
for (int s = 1; s <= n; s++) {
if (color[s] != -1) continue; // already colored
color[s] = 0;
// BFS from s...
}
The graph is bipartite if and only if every component is bipartite. One odd cycle in any component makes the whole answer NO.
Gotcha. Forgetting the outer loop is the most common bug on CSES Building Teams. The problem guarantees \(n\) up to \(10^5\) and the graph can have many components. Always loop over all nodes.
DFS Alternative
You can also 2-color with DFS. The logic is identical: assign the opposite color to each neighbor. If a neighbor already has the same color, return false.
bool dfs(int u, int c, vector<vector<int>>& adj, vector<int>& color) {
color[u] = c;
for (int v : adj[u]) {
if (color[v] == -1) {
if (!dfs(v, 1 - c, adj, color)) return false;
} else if (color[v] == c) {
return false;
}
}
return true;
}
BFS and DFS both work in \(O(n + m)\). BFS is slightly more natural here because bipartiteness is a "layer parity" property, and BFS processes nodes layer by layer. But DFS is fine too.
Odd Cycle Detection
When the bipartite check fails, you've implicitly found an odd cycle. The conflict edge connects two nodes \(u\) and \(v\) at the same BFS distance parity from the source. The odd cycle is: source \(\to \cdots \to u \to v \to \cdots \to\) source (one path through \(u\), the other through \(v\), plus the conflict edge).
Extracting the actual cycle requires tracking parents during BFS, then tracing back from \(u\) and \(v\) to their lowest common ancestor in the BFS tree. The cycle length is \(\text{dist}(u) + \text{dist}(v) + 1\), which is odd because \(\text{dist}(u)\) and \(\text{dist}(v)\) have the same parity.
Application: CSES Building Teams
The problem: \(n\) students, \(m\) friendships. Split students into two teams so that no two friends are on the same team, or report it's impossible.
This is literally the bipartite check. Students are nodes. Friendships are edges. "No two friends on the same team" means no edge connects same-colored nodes. Print the color assignment, or print IMPOSSIBLE.
Connection to Matching Theory
Bipartite graphs have special structure that general graphs don't. One major consequence: König's theorem states that in a bipartite graph, the size of the maximum matching equals the size of the minimum vertex cover. This doesn't hold for general graphs.
You don't need König's theorem for the problems in this chapter. But when you encounter bipartite matching later in the course, remember: the bipartite check you learned here is the gateway to that entire theory.
Try It
The starter code reads a graph and has a TODO for the BFS 2-coloring loop. Fill in the BFS logic.
Predict before running: What happens if you add edge 1-3 to the graph above? Nodes 1 and 3 both have color 0. The edge 1-3 connects same-colored nodes. The triangle 1-2-3 has length 3 (odd). Output: NO.
Challenge: What if the problem asks you to print the odd cycle when the graph is not bipartite? Modify your BFS to track parent pointers. When you find a conflict edge \((u, v)\), trace both \(u\) and \(v\) back to their common ancestor. How do you know the ancestor is common? (Hint: trace both paths back simultaneously until they meet.)
Challenge 2: A graph has \(n\) nodes and no edges. Is it bipartite? What's the 2-coloring? (Every isolated node can be either color. The outer loop assigns each one color 0. Any assignment works --- there are \(2^n\) valid 2-colorings.)
Problems
| Problem | Link | Difficulty |
|---|---|---|
| CSES --- Building Teams | cses.fi/problemset/task/1668 | Easy |
| LC 785 --- Is Graph Bipartite? | leetcode.com/problems/is-graph-bipartite | Medium |
| LC 886 --- Possible Bipartition | leetcode.com/problems/possible-bipartition | Medium |
| AtCoder abc282_d --- Make Bipartite 2 | atcoder.jp/contests/abc282/tasks/abc282_d | Medium |