Bipartite check by two-coloring

Why this matters

Many problems ask you to split things into two groups where some pairs must end up apart. Two people who dislike each other go on different teams. Two exams that share a student go in different time slots. Two jobs that need the same machine go on different machines. In each case there are two sides, and some pairs must be on opposite sides.

A graph whose nodes can be split this way is called bipartite (from Latin roots meaning "two parts"). Deciding whether a graph is bipartite is a standard task. The method is called two-coloring: give every node a colour, either 0 or 1, so that each edge joins two nodes with different colours. If you can do that, the two colours are your two groups. If you cannot, no split exists.

This lesson builds the check in C++ with std::queue for BFS and a std::vector as a stack for DFS. Both run in time proportional to the number of nodes plus the number of edges. The lesson assumes you have read the earlier BFS lessons in this module. The 0-1 BFS lesson uses the same queue pattern, with a deque instead of a plain queue.

Start with the problem: a round table

Suppose six people sit around a round table. Each person must sit next to two others, and the rule is that neighbours must be on different teams. Team 0 takes every other seat, team 1 takes the rest. Start at seat 0 and put person 0 on team 0. Seat 1 is next to seat 0, so person 1 goes on team 1. Seat 2 is next to seat 1, so person 2 goes on team 0. Keep going around. Seat 5 is team 1, and it sits next to seat 0, which is team 0. The rule holds at every seat.

Now try four people around the table. The same rule works: teams 0, 1, 0, 1 around the table. Try three people. Person 0 is team 0. Person 1 is team 1. Person 2 sits next to person 1, so person 2 must be team 0. But person 2 also sits next to person 0, who is team 0. The rule breaks at the last seat.

The difference is the number of seats. A ring of an even number of people always works. A ring of an odd number never does. The rest of this lesson turns that observation into an algorithm for any graph.

The analogy: taking turns

Another way to see the same idea is a game where players take turns. Each player who is "in" must be followed by someone from the other team. If you pass a ball around a circle and every pass changes teams, the ball returns to its starting team only when the number of passes is even. An odd number of passes around a circle lands on the wrong team, and that mismatch is the clash.

Vocabulary before code

• Graph: nodes joined by edges. Here the edges are undirected, which means an edge between a and b can be followed in either direction. Each edge is a rivalry, a conflict or a link that must cross the split.
• Neighbour: a node joined to another node by an edge.
• Colour: a label on a node. In this lesson a colour is 0 or 1, and nothing else. Colour names have no meaning beyond the two groups.
• Two-coloring: giving each node a colour so that no edge joins two nodes of the same colour.
• Bipartite: a graph that has a two-coloring. The word means that its nodes split into two parts with no edges inside a part.
• Cycle: a path that starts and ends at the same node, with no repeated nodes in between. The ring of people above is a cycle.
• Odd cycle: a cycle with an odd number of edges. A triangle is an odd cycle, with three edges.
• Component: a group of nodes that can all reach each other through edges. A graph can have several components, and they are separate from one another.
• Self-loop: an edge from a node to itself. A node with a self-loop is its own rival, so it can never be placed in a group.

The rule in plain words

Start at any uncoloured node and give it colour 0. Look at its neighbours. Each neighbour that is uncoloured gets the opposite colour. Each neighbour that already has a colour must have the opposite colour too. If a neighbour already has the same colour as the node you are looking at, you have found a clash, and the graph is not bipartite.

Then move on to the next node you have coloured and repeat. When every node in the component is coloured without a clash, start on any node that is still uncoloured, because it belongs to a different component. Repeat until every node is coloured.

That is the whole algorithm. Two details need care. First, you must check the neighbour's colour every time, not only when you first colour it. The clash may appear on an edge that closes a loop. Second, you must start a new search for every component. Otherwise nodes in another component stay uncoloured.

Why this works: the proof

We want to show that the check is correct in both directions. If it succeeds, the colouring is valid. If it fails, the graph really has no split.

If the check succeeds, every edge joins different colours. Take any edge between nodes u and v. Our loop looks at every edge leaving every node it colours. So it looks at the edge when it processes u, and again when it processes v. When u is processed, one of two things happens. If v was uncoloured, the check gives it the opposite colour of u, so the edge is fine. If v was already coloured, the check confirmed that its colour is the opposite of u, or it would have stopped. Either way the edge joins different colours. Since every edge is checked, the colouring is valid.

If the check fails, an odd cycle exists. BFS colours each node with the parity of its distance from the start node, measured along the search tree. Parity means whether a number is odd or even. A node at distance 0 gets colour 0, a node at distance 1 gets colour 1, a node at distance 2 gets colour 0, and so on. This holds because every tree edge joins a node to a child one step further away.

A clash happens on an edge u to v where both have the same colour, so both have the same parity of distance from the start. Walk up the search tree from u and from v until you reach their nearest common ancestor. Those two walks have lengths that add to an even number, because the two distances from the start have the same parity. Add the clashing edge u to v. The total number of edges is that even sum plus 1, which is odd. The walks and the edge form a cycle, and that cycle is odd. So a clash means an odd cycle exists, and no two-coloring can exist either.

Together these two parts prove the claim: a graph is bipartite if and only if it has no odd cycle. Apart from a self-loop, which is a cycle of length 1, a triangle is the smallest odd cycle, so any triangle in a graph rules out a split.

Worked example 1: a square and a triangle

The first graph is a square. Its nodes are 0, 1, 2 and 3, and its edges are 0 to 1, 1 to 2, 2 to 3 and 3 to 0. The second is a triangle on nodes 0, 1 and 2. Here is the code.

#include <iostream>
#include <optional>
#include <queue>
#include <string>
#include <vector>
 
using Graph = std::vector<std::vector<int>>;
 
// Returns a colour (0 or 1) for every node, or nothing if the graph has an odd cycle.
std::optional<std::vector<int>> twoColorBfs(const Graph& graph) {
    const int n = static_cast<int>(graph.size());
    std::vector<int> color(n, -1);  // -1 means "not coloured yet"
 
    for (int start = 0; start < n; ++start) {
        if (color[start] != -1) continue;  // already coloured by an earlier search
 
        color[start] = 0;
        std::queue<int> queue;
        queue.push(start);
 
        while (!queue.empty()) {
            int node = queue.front();
            queue.pop();
            for (int next : graph[node]) {
                if (color[next] == -1) {
                    color[next] = 1 - color[node];
                    queue.push(next);
                } else if (color[next] == color[node]) {
                    return std::nullopt;  // two neighbours share a colour
                }
            }
        }
    }
    return color;
}

The function returns std::optional<std::vector<int>>. An optional is a box that holds either a value or nothing. Here it holds the colours when the graph is bipartite, and it holds nothing otherwise. The caller must check which case it got before using the colours.

A small helper prints the colours, or "not bipartite" when the result is empty.

void printResult(const std::string& name, const std::optional<std::vector<int>>& result) {
    std::cout << name << ": ";
    if (!result) {
        std::cout << "not bipartite\n";
        return;
    }
    std::cout << "colors";
    for (int c : *result) std::cout << ' ' << c;
    std::cout << '\n';
}
 
int main() {
    Graph square = {{1, 3}, {0, 2}, {1, 3}, {2, 0}};
    printResult("square bfs", twoColorBfs(square));
 
    Graph triangle = {{1, 2}, {0, 2}, {0, 1}};
    printResult("triangle bfs", twoColorBfs(triangle));
}

Compiled with g++ -std=c++20 -Wall (g++ 15.2.0 on Linux), the program prints:

square bfs: colors 0 1 0 1
triangle bfs: not bipartite

Trace the square by hand. Node 0 gets 0. Its neighbours 1 and 3 get 1. Node 2 is a neighbour of 1, so it gets 0. Node 2's neighbour 3 already has colour 1, which is the opposite of 0, so nothing clashes. The result is 0 1 0 1.

Trace the triangle. Node 0 gets 0. Neighbours 1 and 2 get 1. Node 1 is popped, and its neighbour 2 already has colour 1, the same as node 1. That is the clash. The function returns nothing.

Worked example 2: rivals that form separate groups

The second example has six people and three kinds of relationship. People 0, 1 and 2 form a path: 0 dislikes 1, and 1 dislikes 2. People 3 and 4 dislike each other. Person 5 has no rivals. There are three components. Each one can be coloured on its own, and a component can be flipped without breaking the others.

Graph rivals(6);
auto addRival = [&](int a, int b) {
    rivals[a].push_back(b);
    rivals[b].push_back(a);
};
addRival(0, 1);
addRival(1, 2);
addRival(3, 4);
printResult("rivals bfs", twoColorBfs(rivals));
printResult("rivals dfs", twoColorDfs(rivals));

Output:

rivals bfs: colors 0 1 0 0 1 0
rivals dfs: colors 0 1 0 0 1 0

Both searches agree here. Person 0 gets colour 0, person 1 gets 1, and person 2 gets 0. Person 3 starts a new component and gets 0, and person 4 gets 1. Person 5 starts a component of its own and gets 0. So team 0 is people 0, 2, 3 and 5, and team 1 is people 1 and 4.

The answer is not the only valid one. Each component can swap its two colours, and the result still works. The check only needs one valid answer. If a problem asks for the teams to be balanced in size, you can swap whole components to balance them.

Worked example 3: a grid is always bipartite

A grid of squares is a bipartite graph. Each square touches its neighbours by side, and no two squares that touch by side have the same parity of row plus column. So you can colour a grid like a chessboard, using (row + column) % 2 as the colour.

The check should agree with that pattern. Here is a 3 by 3 grid, with node numbers from 0 to 8, where node row * 3 + column is the square in that row and column.

int side = 3;
Graph grid(side * side);
for (int r = 0; r < side; ++r) {
    for (int c = 0; c < side; ++c) {
        int id = r * side + c;
        if (r + 1 < side) { grid[id].push_back(id + side); grid[id + side].push_back(id); }
        if (c + 1 < side) { grid[id].push_back(id + 1); grid[id + 1].push_back(id); }
    }
}
auto gridColors = twoColorBfs(grid);
printResult("grid bfs", gridColors);

Output:

grid bfs: colors 0 1 0 1 0 1 0 1 0

This matches the chessboard pattern. The four corners and the centre square get colour 0. The centre is two steps from the top left corner, and two is even, so it gets the same colour. The first square gets colour 0 here, so no flip of the whole grid is needed.

Worked example 4: a team split with a clear answer

The last example is the kind of problem you will meet most often. There are six people. Each pair in a ring dislikes its neighbours: 0 and 1, 1 and 2, up to 5 and 0. The ring has six edges, so it is an even cycle, and a split must exist. Then one more dislike is added between 0 and 2. That makes the triangle 0, 1, 2, and no split can exist.

void showTeams(const std::string& name, const Graph& g) {
    auto result = twoColorDfs(g);
    std::cout << name << ": ";
    if (!result) { std::cout << "impossible\n"; return; }
    std::cout << "team 0 =";
    for (int i = 0; i < static_cast<int>(result->size()); ++i) {
        if ((*result)[i] == 0) std::cout << ' ' << i;
    }
    std::cout << "; team 1 =";
    for (int i = 0; i < static_cast<int>(result->size()); ++i) {
        if ((*result)[i] == 1) std::cout << ' ' << i;
    }
    std::cout << '\n';
}

Output:

six people in a ring of dislikes: team 0 = 0 2 4; team 1 = 1 3 5
same ring plus dislike 0-2: impossible
path of four: team 0 = 0 2; team 1 = 1 3

The first answer puts people 0, 2 and 4 on one team and 1, 3 and 5 on the other. Every dislike pair crosses the teams. The second answer is "impossible", and the reason is the triangle 0, 1, 2, which needs three teams. The third example is a plain path of four people, which splits as 0 and 2 against 1 and 3.

When the answer is impossible, the usual next question is which dislike to drop so that a split becomes possible. That is a different problem, and this lesson does not solve it.

DFS instead of BFS

The same check works with depth-first search (DFS), which goes as deep as it can along one path before backing up. The version in this lesson uses an explicit std::vector as a stack, not recursion. Recursion would use the call stack, and a long path, such as a line of 100,000 people, could run out of space. A stack in a vector has no such limit beyond memory.

std::optional<std::vector<int>> twoColorDfs(const Graph& graph) {
    const int n = static_cast<int>(graph.size());
    std::vector<int> color(n, -1);
 
    for (int start = 0; start < n; ++start) {
        if (color[start] != -1) continue;
        color[start] = 0;
        std::vector<int> stack{start};
        while (!stack.empty()) {
            int node = stack.back();
            stack.pop_back();
            for (int next : graph[node]) {
                if (color[next] == -1) {
                    color[next] = 1 - color[node];
                    stack.push_back(next);
                } else if (color[next] == color[node]) {
                    return std::nullopt;
                }
            }
        }
    }
    return color;
}

The proof works unchanged. Each node gets the opposite colour of the node that discovered it, so colours still follow the parity of depth in the tree the search builds, and the clash argument applies. Use whichever search you find easier to read. Both take time proportional to the nodes plus the edges.

Common mistakes

Mistake 1: starting the search only from node 0. A graph can have components that do not touch node 0. If you start once, those nodes keep colour -1. Here is a version that starts only from node 0, run on the rival graph from example 2.

A: 0 1 0 -1 -1 -1

Nodes 3, 4 and 5 are still -1, which means "not coloured". Those nodes were never checked, so the output looks like a split but is not one. Loop over every node as a possible start, as the code does.

Mistake 2: leaving out the clash check. Some people colour nodes and forget to test whether a neighbour already has the same colour. On the triangle, that version returns a colouring anyway.

B: 0 1 1

Nodes 1 and 2 both have colour 1, and they are neighbours. The output claims a split that does not exist. The check on color[next] == color[node] is what makes the answer correct.

Mistake 3: checking the clash only when a node is first coloured. If the check runs only in the branch where color[next] is -1, it misses edges that close a loop. A triangle's last edge always joins two nodes that are already coloured. Put the clash test in the branch where the neighbour already has a colour.

Mistake 4: treating a directed graph as undirected. The method assumes that each edge is a two-way relationship. Rivalries and conflicts are two-way, so store each one in both directions, as the example code does with addRival. If your input has one-way edges, add the reverse edge yourself before you call the check, or the answer is about a different graph.

Mistake 5: using the value without checking the optional. The function returns an optional, and you cannot use the colours until you know it holds a value. Here is a version that tries to assign the result directly to a plain vector, with the same graph as in example 1. g++ 15.2.0 rejects it.

std::vector<int> bad = twoColorBfs(square2);

The compiler message is:

bad.cpp: In function ‘int main()’:
bad.cpp:4:39: error: conversion from ‘std::optional<std::vector<int> >’ to non-scalar type ‘std::vector<int>’ requested
    4 |     std::vector<int> bad = twoColorBfs(square2);
      |                            ~~~~~~~~~~~^~~~~~~~~

Read the result with if (result) first, or use result.has_value(), and only then read *result.

Mistake 6: forgetting self-loops. An edge from a node to itself means the node must differ from itself, which is impossible. The check catches it, because the neighbour is the node itself and already has the same colour. Do not remove self-loops from the input to make the check pass. They make the answer correct.

Practice

Exercise 1. Is a cycle of five people around a table bipartite? What about six people? Explain with the parity argument.

Show the answer

A cycle of five is not bipartite. Going around the ring from one person back to the same person takes five steps, and each step must change the colour. An odd number of changes cannot end on the starting colour. A cycle of six is bipartite, because six changes return to the start colour exactly.

Exercise 2. Graph A has edges 0-1, 1-2, 2-3 and 3-0. Graph B has edges 0-1, 1-2, 2-0 and 2-3. Which is bipartite? Give the reason for each.

Show the answer

Graph A is bipartite. It is a square, which is an even cycle, and the colours are 0 1 0 1. Graph B is not bipartite. It contains the triangle 0, 1, 2, which is an odd cycle, so no two-coloring exists.

Exercise 3. A two-by-four grid of squares has eight nodes. Without running the check, state its colours, using the chessboard pattern with the top left square as colour 0. Then say whether the check would accept it.

Show the answer

Use (row + column) % 2. The top row is 0 1 0 1, and the bottom row is 1 0 1 0. Every square touches its neighbours by side, and neighbours always differ in row plus column by 1, so the colours differ. The check accepts the grid.

Exercise 4. Using the rivals graph from example 2, which people go on team 0 and which on team 1 in the colouring the code produces? Then name one other valid split for the same graph.

Show the answer

The code gives team 0 as people 0, 2, 3 and 5, and team 1 as people 1 and 4. Another valid split flips only the path 0-1-2. Then team 0 is people 1, 3 and 5, and team 1 is people 0, 2 and 4. Check the three edges of the path: 0 and 1 are on different teams, and so are 1 and 2. The pair 3-4 is still split, and person 5 has no rivals, so it can go on either side.

Exercise 5. Why does the outer loop over start nodes need to continue after the first search ends? Give an example where skipping it gives a wrong answer.

Show the answer

Each component of a graph is separate, so a search that starts in one component never reaches the others. Without the outer loop, nodes in the other components keep colour -1. The output would then have uncoloured nodes, and the check would never have examined their edges, so a triangle in another component would go unnoticed. The rivals graph in example 2 is such a case: a triangle added to nodes 3, 4 and 5 would be missed if the search stopped after node 0.

Summary

• A graph is bipartite exactly when it has no odd cycle, which is the same as saying it can be two-coloured.
• BFS or DFS colours nodes so that neighbours differ, and a neighbour with the same colour signals failure.
• Start a search from every uncoloured node, so every component is handled.
• The clash test must run every time an edge is examined, including edges that close a loop.
• A self-loop or an odd cycle such as a triangle makes the answer impossible.
• The check runs in time proportional to nodes plus edges, and each component can have its two colours swapped without breaking the split.