33.05Intermediate / Advanced4 topics15 min4 interactive animations

Bipartiteness

A graph is bipartite when its vertices can be split into two sides with every edge crossing; BFS or DFS two-colouring decides it, and an odd cycle is the exact obstruction.

Learning goals

Two-colour a graph with BFS or DFS and report failure on a clash
Extract an odd cycle as proof that a graph is not bipartite
Check every component of a disconnected graph
Recognise problems that hide a bipartite check

Prerequisites

Breadth-first searchDepth-first searchConnected components

Can the students be split into two teams so that no one is on a team with an enemy? Can jobs be given to two machines without a clash? Each is a two-colouring question.

33.05.1

Two-coloring

Give the start vertex colour 0. Every neighbour must get the opposite colour, their neighbours the colour of the start, and so on. If an edge ever joins two vertices of the *same* colour, no valid colouring exists. If the search ends without a clash, the colouring is a valid split into two sides.

The colouring is forced: once the start colour is chosen, each vertex in its component has exactly one possible colour. That is why a single greedy pass decides the question. Open *Two-colour (bipartite check)* in the animation and compare the even cycle with the triangle.

Java

1static boolean tryColour(List<List<Integer>> g, int[] colour, int s) {   // colour is -1 where unvisited; returns false on a clash
2    Deque<Integer> queue = new ArrayDeque<>();
3    colour[s] = 0;
4    queue.add(s);
5    while (!queue.isEmpty()) {
6        int u = queue.poll();
7        for (int v : g.get(u)) {
8            if (colour[v] == -1) { colour[v] = 1 - colour[u]; queue.add(v); }
9            else if (colour[v] == colour[u]) return false;      // both ends of an edge on the same side
10        }
11    }
12    return true;
13}

Components, two-colouring and cycle detection in an undirected graph

Interactive · edit the input

undirected graph · 8 vertices · 6 edges

Colour / component AColour / component BComponent CConflictBeing expanded

component of each vertex

-0

-1

-2

-3

-4

-5

-6

-7

Setup

Search from an unlabelled vertex: everything the search reaches is one component. Repeat from the next unlabelled vertex until every vertex has a label.

Step 1 / 13

Java

1int[] components(List<List<Integer>> g) {        // component id per vertex
2    int n = g.size(); int[] comp = new int[n]; Arrays.fill(comp, -1);
3    int id = 0;
4    for (int s = 0; s < n; s++) {
5        if (comp[s] != -1) continue;
6        Deque<Integer> q = new ArrayDeque<>(); q.add(s); comp[s] = id;
7        while (!q.isEmpty()) {
8            int u = q.poll();
9            for (int v : g.get(u)) if (comp[v] == -1) { comp[v] = id; q.add(v); }
10        }
11        id++;                                    // the search ended: one whole component labelled
12    }
13    return comp;
14}
15boolean isBipartite(List<List<Integer>> g) {
16    int n = g.size(); int[] color = new int[n]; Arrays.fill(color, -1);
17    for (int s = 0; s < n; s++) {                // check every component
18        if (color[s] != -1) continue;
19        color[s] = 0; Deque<Integer> q = new ArrayDeque<>(); q.add(s);
20        while (!q.isEmpty()) {
21            int u = q.poll();
22            for (int v : g.get(u)) {
23                if (color[v] == -1) { color[v] = color[u] ^ 1; q.add(v); }
24                else if (color[v] == color[u]) return false;        // an odd cycle
25            }
26        }
27    }
28    return true;
29}
30boolean hasCycle(int n, List<int[]>[] g) {       // undirected; g[u] holds {v, edgeId}
31    boolean[] seen = new boolean[n];
32    for (int s = 0; s < n; s++) if (!seen[s] && dfsCycle(g, s, -1, seen)) return true;
33    return false;
34}
35boolean dfsCycle(List<int[]>[] g, int u, int viaEdge, boolean[] seen) {
36    seen[u] = true;
37    for (int[] e : g[u]) {
38        if (e[1] == viaEdge) continue;           // do not walk back along the edge we came by
39        if (seen[e[0]] || dfsCycle(g, e[0], e[1], seen)) return true;   // a seen vertex reached by another edge: a cycle
40    }
41    return false;
42}

Live state

0 components0 vertices visited

vertices

edges

No condition evaluated on this step

Execution trace (dry run table)Show 13 steps

Step	Line	State	What happens
1	L2	vertices=8 edges=6	Search from an unlabelled vertex: everything the search reaches is one component. Repeat from the next unlabelled vertex until every vertex has a label.
2	L6	start=0 component=0	Vertex 0 is unlabelled: start component C1 here.
3	L9	u=0 v=1 component=0	0 - 1: 1 is unlabelled, so it belongs to C1 too.
4	L9	u=1 v=2 component=0	1 - 2: 2 is unlabelled, so it belongs to C1 too.
5	L11	components=1	The queue is empty: component C1 is complete. 1 so far.
6	L6	start=3 component=1	Vertex 3 is unlabelled: start component C2 here.
7	L9	u=3 v=4 component=1	3 - 4: 4 is unlabelled, so it belongs to C2 too.
8	L11	components=2	The queue is empty: component C2 is complete. 2 so far.
9	L6	start=5 component=2	Vertex 5 is unlabelled: start component C3 here.
10	L9	u=5 v=6 component=2	5 - 6: 6 is unlabelled, so it belongs to C3 too.
11	L9	u=5 v=7 component=2	5 - 7: 7 is unlabelled, so it belongs to C3 too.
12	L11	components=3	The queue is empty: component C3 is complete. 3 so far.
13	L13	return=3 sizes=[3, 2, 3]	3 components with sizes [3, 2, 3]. A vertex with no edge is a component of size 1. Cost O(V + E).

33.05.2

BFS/DFS coloring

BFS and DFS both work because the only thing that matters is that each vertex is coloured from a neighbour that was already coloured. BFS assigns colour by the parity of the distance from the start. DFS passes the opposite colour down each call.

Pick whichever is more convenient. DFS is shorter to write recursively; BFS avoids deep recursion. Both run in O(n + m).

Java

1static boolean colourByDfs(List<List<Integer>> g, int[] colour, int u, int c) {
2    colour[u] = c;
3    for (int v : g.get(u)) {
4        if (colour[v] == -1) { if (!colourByDfs(g, colour, v, 1 - c)) return false; }
5        else if (colour[v] == c) return false;                   // a neighbour on the same side
6    }
7    return true;
8}

Components, two-colouring and cycle detection in an undirected graph

Interactive · edit the input

undirected graph · 8 vertices · 6 edges

Colour / component AColour / component BComponent CConflictBeing expanded

component of each vertex

-0

-1

-2

-3

-4

-5

-6

-7

Setup

Search from an unlabelled vertex: everything the search reaches is one component. Repeat from the next unlabelled vertex until every vertex has a label.

Step 1 / 13

Java

1int[] components(List<List<Integer>> g) {        // component id per vertex
2    int n = g.size(); int[] comp = new int[n]; Arrays.fill(comp, -1);
3    int id = 0;
4    for (int s = 0; s < n; s++) {
5        if (comp[s] != -1) continue;
6        Deque<Integer> q = new ArrayDeque<>(); q.add(s); comp[s] = id;
7        while (!q.isEmpty()) {
8            int u = q.poll();
9            for (int v : g.get(u)) if (comp[v] == -1) { comp[v] = id; q.add(v); }
10        }
11        id++;                                    // the search ended: one whole component labelled
12    }
13    return comp;
14}
15boolean isBipartite(List<List<Integer>> g) {
16    int n = g.size(); int[] color = new int[n]; Arrays.fill(color, -1);
17    for (int s = 0; s < n; s++) {                // check every component
18        if (color[s] != -1) continue;
19        color[s] = 0; Deque<Integer> q = new ArrayDeque<>(); q.add(s);
20        while (!q.isEmpty()) {
21            int u = q.poll();
22            for (int v : g.get(u)) {
23                if (color[v] == -1) { color[v] = color[u] ^ 1; q.add(v); }
24                else if (color[v] == color[u]) return false;        // an odd cycle
25            }
26        }
27    }
28    return true;
29}
30boolean hasCycle(int n, List<int[]>[] g) {       // undirected; g[u] holds {v, edgeId}
31    boolean[] seen = new boolean[n];
32    for (int s = 0; s < n; s++) if (!seen[s] && dfsCycle(g, s, -1, seen)) return true;
33    return false;
34}
35boolean dfsCycle(List<int[]>[] g, int u, int viaEdge, boolean[] seen) {
36    seen[u] = true;
37    for (int[] e : g[u]) {
38        if (e[1] == viaEdge) continue;           // do not walk back along the edge we came by
39        if (seen[e[0]] || dfsCycle(g, e[0], e[1], seen)) return true;   // a seen vertex reached by another edge: a cycle
40    }
41    return false;
42}

Live state

0 components0 vertices visited

vertices

edges

No condition evaluated on this step

Execution trace (dry run table)Show 13 steps

Step	Line	State	What happens
1	L2	vertices=8 edges=6	Search from an unlabelled vertex: everything the search reaches is one component. Repeat from the next unlabelled vertex until every vertex has a label.
2	L6	start=0 component=0	Vertex 0 is unlabelled: start component C1 here.
3	L9	u=0 v=1 component=0	0 - 1: 1 is unlabelled, so it belongs to C1 too.
4	L9	u=1 v=2 component=0	1 - 2: 2 is unlabelled, so it belongs to C1 too.
5	L11	components=1	The queue is empty: component C1 is complete. 1 so far.
6	L6	start=3 component=1	Vertex 3 is unlabelled: start component C2 here.
7	L9	u=3 v=4 component=1	3 - 4: 4 is unlabelled, so it belongs to C2 too.
8	L11	components=2	The queue is empty: component C2 is complete. 2 so far.
9	L6	start=5 component=2	Vertex 5 is unlabelled: start component C3 here.
10	L9	u=5 v=6 component=2	5 - 6: 6 is unlabelled, so it belongs to C3 too.
11	L9	u=5 v=7 component=2	5 - 7: 7 is unlabelled, so it belongs to C3 too.
12	L11	components=3	The queue is empty: component C3 is complete. 3 so far.
13	L13	return=3 sizes=[3, 2, 3]	3 components with sizes [3, 2, 3]. A vertex with no edge is a component of size 1. Cost O(V + E).

33.05.3

Odd cycle obstruction

A graph is bipartite **if and only if** it has no cycle of odd length. Going around a cycle the colours must alternate, so an odd number of steps would end on the wrong colour. Conversely, if BFS finds a clash between u and v in the same layer, climbing both parent chains to their meeting point gives an odd cycle: the two climbs have equal length k, plus the clash edge, makes 2k + 1.

Returning that cycle, not just false, is a proof that can be checked by hand. A self-loop is an odd cycle of length 1, so a graph with a loop is never bipartite.

Java

1static List<Integer> oddCycle(List<List<Integer>> g) {          // an odd cycle as a list of vertices, or empty if bipartite
2    int n = g.size();
3    int[] colour = new int[n], parent = new int[n];
4    Arrays.fill(colour, -1);
5    for (int s = 0; s < n; s++) {
6        if (colour[s] != -1) continue;
7        Deque<Integer> queue = new ArrayDeque<>();
8        colour[s] = 0; parent[s] = -1;
9        queue.add(s);
10        while (!queue.isEmpty()) {
11            int u = queue.poll();
12            for (int v : g.get(u)) {
13                if (colour[v] == -1) { colour[v] = 1 - colour[u]; parent[v] = u; queue.add(v); }
14                else if (colour[v] == colour[u]) {                // same layer: climb both sides to the meeting vertex
15                    List<Integer> left = new ArrayList<>(), right = new ArrayList<>();
16                    int a = u, b = v;
17                    while (a != b) { left.add(a); right.add(b); a = parent[a]; b = parent[b]; }
18                    left.add(a);                                  // the meeting vertex
19                    Collections.reverse(right);
20                    left.addAll(right);                           // meeting vertex ... u, then v ... back down
21                    return left;
22                }
23            }
24        }
25    }
26    return new ArrayList<>();
27}

Components, two-colouring and cycle detection in an undirected graph

Interactive · edit the input

undirected graph · 8 vertices · 6 edges

Colour / component AColour / component BComponent CConflictBeing expanded

component of each vertex

-0

-1

-2

-3

-4

-5

-6

-7

Setup

Search from an unlabelled vertex: everything the search reaches is one component. Repeat from the next unlabelled vertex until every vertex has a label.

Step 1 / 13

Java

1int[] components(List<List<Integer>> g) {        // component id per vertex
2    int n = g.size(); int[] comp = new int[n]; Arrays.fill(comp, -1);
3    int id = 0;
4    for (int s = 0; s < n; s++) {
5        if (comp[s] != -1) continue;
6        Deque<Integer> q = new ArrayDeque<>(); q.add(s); comp[s] = id;
7        while (!q.isEmpty()) {
8            int u = q.poll();
9            for (int v : g.get(u)) if (comp[v] == -1) { comp[v] = id; q.add(v); }
10        }
11        id++;                                    // the search ended: one whole component labelled
12    }
13    return comp;
14}
15boolean isBipartite(List<List<Integer>> g) {
16    int n = g.size(); int[] color = new int[n]; Arrays.fill(color, -1);
17    for (int s = 0; s < n; s++) {                // check every component
18        if (color[s] != -1) continue;
19        color[s] = 0; Deque<Integer> q = new ArrayDeque<>(); q.add(s);
20        while (!q.isEmpty()) {
21            int u = q.poll();
22            for (int v : g.get(u)) {
23                if (color[v] == -1) { color[v] = color[u] ^ 1; q.add(v); }
24                else if (color[v] == color[u]) return false;        // an odd cycle
25            }
26        }
27    }
28    return true;
29}
30boolean hasCycle(int n, List<int[]>[] g) {       // undirected; g[u] holds {v, edgeId}
31    boolean[] seen = new boolean[n];
32    for (int s = 0; s < n; s++) if (!seen[s] && dfsCycle(g, s, -1, seen)) return true;
33    return false;
34}
35boolean dfsCycle(List<int[]>[] g, int u, int viaEdge, boolean[] seen) {
36    seen[u] = true;
37    for (int[] e : g[u]) {
38        if (e[1] == viaEdge) continue;           // do not walk back along the edge we came by
39        if (seen[e[0]] || dfsCycle(g, e[0], e[1], seen)) return true;   // a seen vertex reached by another edge: a cycle
40    }
41    return false;
42}

Live state

0 components0 vertices visited

vertices

edges

No condition evaluated on this step

Execution trace (dry run table)Show 13 steps

Step	Line	State	What happens
1	L2	vertices=8 edges=6	Search from an unlabelled vertex: everything the search reaches is one component. Repeat from the next unlabelled vertex until every vertex has a label.
2	L6	start=0 component=0	Vertex 0 is unlabelled: start component C1 here.
3	L9	u=0 v=1 component=0	0 - 1: 1 is unlabelled, so it belongs to C1 too.
4	L9	u=1 v=2 component=0	1 - 2: 2 is unlabelled, so it belongs to C1 too.
5	L11	components=1	The queue is empty: component C1 is complete. 1 so far.
6	L6	start=3 component=1	Vertex 3 is unlabelled: start component C2 here.
7	L9	u=3 v=4 component=1	3 - 4: 4 is unlabelled, so it belongs to C2 too.
8	L11	components=2	The queue is empty: component C2 is complete. 2 so far.
9	L6	start=5 component=2	Vertex 5 is unlabelled: start component C3 here.
10	L9	u=5 v=6 component=2	5 - 6: 6 is unlabelled, so it belongs to C3 too.
11	L9	u=5 v=7 component=2	5 - 7: 7 is unlabelled, so it belongs to C3 too.
12	L11	components=3	The queue is empty: component C3 is complete. 3 so far.
13	L13	return=3 sizes=[3, 2, 3]	3 components with sizes [3, 2, 3]. A vertex with no edge is a component of size 1. Cost O(V + E).

33.05.4

Component-by-component checking

A disconnected graph is bipartite only if **every** component is. Starting one search is not enough: loop over all vertices and start a new colouring from each uncoloured one, as in the component count. Different components can use their colours independently, so no clash can arise between them.

Forgetting this loop is a common bug: the check passes on the component of vertex 0 and misses an odd cycle elsewhere. The animation's two-colour preset has a separate component to show the loop.

Java

1static boolean bipartiteAllComponents(List<List<Integer>> g) {
2    int[] colour = new int[g.size()];
3    Arrays.fill(colour, -1);
4    for (int s = 0; s < g.size(); s++) {
5        if (colour[s] != -1) continue;                           // already coloured as part of an earlier component
6        Deque<Integer> queue = new ArrayDeque<>();
7        colour[s] = 0;
8        queue.add(s);
9        while (!queue.isEmpty()) {
10            int u = queue.poll();
11            for (int v : g.get(u)) {
12                if (colour[v] == -1) { colour[v] = 1 - colour[u]; queue.add(v); }
13                else if (colour[v] == colour[u]) return false;
14            }
15        }
16    }
17    return true;
18}

Components, two-colouring and cycle detection in an undirected graph

Interactive · edit the input

undirected graph · 8 vertices · 6 edges

Colour / component AColour / component BComponent CConflictBeing expanded

component of each vertex

-0

-1

-2

-3

-4

-5

-6

-7

Setup

Search from an unlabelled vertex: everything the search reaches is one component. Repeat from the next unlabelled vertex until every vertex has a label.

Step 1 / 13

Java

1int[] components(List<List<Integer>> g) {        // component id per vertex
2    int n = g.size(); int[] comp = new int[n]; Arrays.fill(comp, -1);
3    int id = 0;
4    for (int s = 0; s < n; s++) {
5        if (comp[s] != -1) continue;
6        Deque<Integer> q = new ArrayDeque<>(); q.add(s); comp[s] = id;
7        while (!q.isEmpty()) {
8            int u = q.poll();
9            for (int v : g.get(u)) if (comp[v] == -1) { comp[v] = id; q.add(v); }
10        }
11        id++;                                    // the search ended: one whole component labelled
12    }
13    return comp;
14}
15boolean isBipartite(List<List<Integer>> g) {
16    int n = g.size(); int[] color = new int[n]; Arrays.fill(color, -1);
17    for (int s = 0; s < n; s++) {                // check every component
18        if (color[s] != -1) continue;
19        color[s] = 0; Deque<Integer> q = new ArrayDeque<>(); q.add(s);
20        while (!q.isEmpty()) {
21            int u = q.poll();
22            for (int v : g.get(u)) {
23                if (color[v] == -1) { color[v] = color[u] ^ 1; q.add(v); }
24                else if (color[v] == color[u]) return false;        // an odd cycle
25            }
26        }
27    }
28    return true;
29}
30boolean hasCycle(int n, List<int[]>[] g) {       // undirected; g[u] holds {v, edgeId}
31    boolean[] seen = new boolean[n];
32    for (int s = 0; s < n; s++) if (!seen[s] && dfsCycle(g, s, -1, seen)) return true;
33    return false;
34}
35boolean dfsCycle(List<int[]>[] g, int u, int viaEdge, boolean[] seen) {
36    seen[u] = true;
37    for (int[] e : g[u]) {
38        if (e[1] == viaEdge) continue;           // do not walk back along the edge we came by
39        if (seen[e[0]] || dfsCycle(g, e[0], e[1], seen)) return true;   // a seen vertex reached by another edge: a cycle
40    }
41    return false;
42}

Live state

0 components0 vertices visited

vertices

edges

No condition evaluated on this step

Execution trace (dry run table)Show 13 steps

Step	Line	State	What happens
1	L2	vertices=8 edges=6	Search from an unlabelled vertex: everything the search reaches is one component. Repeat from the next unlabelled vertex until every vertex has a label.
2	L6	start=0 component=0	Vertex 0 is unlabelled: start component C1 here.
3	L9	u=0 v=1 component=0	0 - 1: 1 is unlabelled, so it belongs to C1 too.
4	L9	u=1 v=2 component=0	1 - 2: 2 is unlabelled, so it belongs to C1 too.
5	L11	components=1	The queue is empty: component C1 is complete. 1 so far.
6	L6	start=3 component=1	Vertex 3 is unlabelled: start component C2 here.
7	L9	u=3 v=4 component=1	3 - 4: 4 is unlabelled, so it belongs to C2 too.
8	L11	components=2	The queue is empty: component C2 is complete. 2 so far.
9	L6	start=5 component=2	Vertex 5 is unlabelled: start component C3 here.
10	L9	u=5 v=6 component=2	5 - 6: 6 is unlabelled, so it belongs to C3 too.
11	L9	u=5 v=7 component=2	5 - 7: 7 is unlabelled, so it belongs to C3 too.
12	L11	components=3	The queue is empty: component C3 is complete. 3 so far.
13	L13	return=3 sizes=[3, 2, 3]	3 components with sizes [3, 2, 3]. A vertex with no edge is a component of size 1. Cost O(V + E).

Practice ladder

Now try it yourself

Easy

Find if Path Exists in Graph

Medium

Is Graph Bipartite?
Possible Bipartition

Advanced

Divide Nodes Into the Maximum Number of Groups

Key takeaways

Bipartite means two-colourable: every edge joins different colours.
BFS or DFS colouring is forced once the first colour is chosen; a clash means failure.
A graph is bipartite if and only if it has no odd cycle, and the clash gives one.
Start a colouring in every component.