Bipartite graphs

A graph is bipartite if its vertices can be coloured with two colours so that every edge joins two different colours. Breadth-first search checks this in O(n + m) by giving each newly reached vertex the colour opposite to the vertex it was reached from; when it fails, the graph has a cycle of odd length. To pair up the vertices of one colour with the vertices of the other, see maximum matching instead.

Explanation

A teacher splits a class of 5 children into two teams for a game, and two children who have quarrelled must play in different teams. There are 4 quarrels: 1 and 2, 2 and 3, 2 and 4, 4 and 5.

Put child 1 in team A. Every other child's team then follows from the quarrels, and nobody has a choice.

Fig. 1. Team A is blue, team B is amber.

A real class has more quarrels, and they can go round in a circle. This class has 8 children, and the teacher has the 8 quarrels as a list. Can the class be split, and which team is child 5 in?

Fig. 2. Can the 8 children be split into two teams so that every quarrel is between the teams?

The obvious way is to go down the list and separate each pair: if neither child has a team, the first goes to team A and the second to team B; otherwise the child without a team goes opposite the other. The first five quarrels go fine. At the sixth, 5 and 7, neither child has a team, so child 5 goes to team A and child 7 to team B. Child 8 got team A from child 4, so the seventh quarrel, 5 and 8, is inside team A, and the list says "impossible".

Fig. 3. The quarrel 5–8 is inside team A.

A split exists, with child 5 in team B, but going down the list guessed the team of child 5 before anything tied it to the children already placed.

So the question is how to place every child without a guess. Start with one child, and give a team only to a child who quarrelled with someone already placed, in the order they were placed, the way breadth-first search spreads.

In graph terms, a graph that can be split like this is bipartite. To check it, colour the start, give every newly reached neighbour the other colour, and check that every edge joins two different colours.

Let's run the search on the class of 8, with the children waiting to be taken in a queue (first in, first out) below the class.

Child 1 is put in team A (blue) and joins the queue. A team just given is drawn in red.

Child 1 is taken from the front of the queue (marked $v$).

Child 2 quarrelled with child 1 and has no team, so it goes to team B (amber), the other team, and joins the queue.

Child 6 quarrelled with child 1 and has no team, so it goes to team B, the other team, and joins the queue.

Child 2 is taken from the front of the queue.

Child 3 quarrelled with child 2 and has no team, so it goes to team A, the other team, and joins the queue.

Child 6 is taken from the front of the queue.

Child 7 quarrelled with child 6 and has no team, so it goes to team A, the other team, and joins the queue.

Child 3 is taken from the front of the queue.

Child 4 quarrelled with child 3 and has no team, so it goes to team B, the other team, and joins the queue.

Child 7 is taken from the front of the queue.

Child 5 quarrelled with child 7 and has no team, so it goes to team B, the other team, and joins the queue.

Child 4 is taken from the front of the queue.

Child 8 quarrelled with child 4 and has no team, so it goes to team A, the other team, and joins the queue.

Child 5 is taken from the front of the queue.

Child 8 is in team A and child 5 in team B: different teams, fine.

Child 8 is taken from the front of the queue.

Child 5 is in team B and child 8 in team A: different teams, fine.

The queue is empty: every quarrel joins two different teams, so the class can be split.

1/19

Fig. 4. Step through with the buttons or the arrow keys. A grey arrow is the check of a quarrel between two children who already have teams.

The run gives the whole split: team A is children 1, 3, 7 and 8, team B is children 2, 4, 5 and 6. The two routes round the circle from child 1 reach the quarrel 5–8 from both ends and give children 5 and 8 different teams.

Now add a quarrel between children 2 and 5. Child 2 finds children 3 and 5, both team A, and child 6 finds child 7, also team A. Their quarrel 5–7 is inside team A.

Fig. 5. The new quarrel 2–5 closes a circle of 5 children (red).

On a circle of 5, the two routes from the start always put the two ends of some quarrel in the same team. That quarrel need not be the new one: here it is 5–7. Starting child 1 in team B only swaps every team, so children 5 and 7 still end up together.

A circle of quarrels is a cycle, and a cycle with an odd number of vertices is an odd cycle. A graph is bipartite exactly when it has no odd cycle. A cycle by itself is fine, unlike in cycle detection: the class of 8 has one and splits.

Implementation

In code, children are vertices, quarrels are edges of the graph, and teams A and B are colours 1 and 2. Let's keep the colours in an array color: color[v] is 0 while v is not coloured yet, then 1 or 2, and 3 - color[v] is the other colour. This one array marks the vertices the search has reached and holds the answer.

A search colours only the part of the graph it reaches, so, as when counting connected components, a new search starts from every vertex that is still uncoloured. Colour 1 at a new start is a free choice: no edge joins the new component to the vertices already coloured, so nothing can clash with them, unlike child 5, whom the quarrel 5–8 tied to child 8.

1. Initialise: color[v] = 0 for every vertex, bipartite = true.

2. Start a new component: for s = 1 to n, if color[s] == 0, set color[s] = 1 and push s to the queue.

3. Take the next vertex v from the front of the queue.

4. Expand its edges: look at each neighbour u of v.

5. Colour it: if color[u] == 0, set color[u] = 3 - color[v] and push u.

6. Check the edge: otherwise, if color[u] == color[v], the graph is not bipartite.

7. Stop: a search ends when the queue is empty; with no conflict anywhere, the graph is bipartite.

The program reads n and m, then m edges u v, with vertices from 1 to n. The edges have no direction: a directed input is read as two-way edges, and an edge from a vertex to itself makes the answer NO. The program prints YES and the colour of every vertex, or NO. For the class of 8 the input is:

8 8
1 2
1 6
2 3
3 4
4 8
5 7
5 8
6 7

The graph is stored as an adjacency list, where adj[v] lists the neighbours of v.

#include <iostream>
#include <queue>
#include <vector>
using namespace std;

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);
    }

    // initialise
    vector<int> color(n + 1, 0);   // 0: not coloured yet
    bool bipartite = true;

    for (int s = 1; s <= n && bipartite; s++) {
        if (color[s] != 0) continue;   // already coloured: skip

        // start a new component
        color[s] = 1;
        queue<int> q;
        q.push(s);

        while (!q.empty() && bipartite) {   // stop: when the queue is empty
            // take the next vertex
            int v = q.front();
            q.pop();

            // expand its edges
            for (int u : adj[v]) {
                if (color[u] == 0) {
                    // colour it
                    color[u] = 3 - color[v];
                    q.push(u);
                }
                // check the edge
                else if (color[u] == color[v]) bipartite = false;
            }
        }
    }

    if (!bipartite) {
        cout << "NO\n";
        return 0;
    }
    cout << "YES\n";
    for (int v = 1; v <= n; v++) {
        cout << color[v] << (v < n ? ' ' : '\n');
    }
}

A recursive depth-first search colours the same way. Every vertex is taken once and every edge is checked from each end, so the check takes O(n + m) time and memory.

Team sizes and the number of splits

A component has exactly two splits: the one the search finds, and the same with its colours swapped. A bipartite graph with k components, isolated vertices included, has 2^k splits.

To make one colour as large as possible, take the larger colour of every component. Count each colour of the current component in cnt[1] and cnt[2], and add the larger count to largest. These lines go into the program above:

#include <algorithm>                       // for max

int largest = 0;                           // after: bool bipartite = true;

int cnt[3] = {0, 1, 0};                    // start a new component, after: color[s] = 1;

cnt[color[u]]++;                           // colour it, after: color[u] = 3 - color[v];

largest += max(cnt[1], cnt[2]);            // after the while loop, inside the for loop

cout << largest << '\n';                   // at the end

With an extra edge 9–10 next to the class of 8, there are 2 components, 2^2 = 4 splits, and the largest colour has 4 + 1 = 5 vertices.

Graphs that are always bipartite

Some graphs are known to be bipartite in advance. A tree has no cycles at all, so the search never finds a conflict. A grid where squares sharing a side are neighbours is coloured like a chessboard, by whether row + column is even; a side step changes row + column by 1, so it lands on the other colour.

Fig. 6. Squares that share a side always have different colours.

Correctness proof

If the search ends with no conflict, every edge was checked and joins two different colours, so the colours are a valid split.

If it finds a conflict, no split exists. Every colour in a component is forced by the start, so any split puts the same vertices together, and the conflict edge joins two of them.

The conflict also shows an odd cycle. In BFS a vertex's colour tells whether its distance from the start is even or odd, and an edge joins vertices whose distances differ by at most 1, so the ends of a conflict edge have the same distance $d$. Follow the links to the vertex each was found from, back from both ends; both chains lead to the start, so they meet. The two chains have the same length, so together with the conflict edge they make a cycle of odd length, at most 2d + 1.

Fig. 7. Vertices 5 and 7 are both 2 edges away from vertex 1. Their two chains and the edge between them make a cycle of 2 + 2 + 1 = 5.

An odd cycle can't be split: going round it, the colours alternate, so an odd number of steps ends back at the start with the other colour. Together, these cases show that a graph is bipartite exactly when it has no odd cycle.

Similar algorithms

Cycle detection asks whether a graph has any cycle; a bipartite graph can have many, all of even length.

When edges arrive one by one with "can it still be split?" after each, a disjoint set union that remembers whether a vertex has the same colour as its leader answers each in O(\log n) time or faster, instead of a new search each time.

Colouring with three or more colours has no known method that avoids trying the choices, so small graphs are solved by backtracking.

Pairing vertices of one colour with vertices of the other, as many pairs as possible, is maximum matching, solved with maximum flow.

Practice