Bipartite colouring
BFS/DFS painting neighbours the opposite colour; a clash means odd cycle.
Every discovered edge joins two different colours.
01The intuition
Start with what you would do by hand
Six students must be split into two teams, and certain pairs refuse to be on the same team: (0,1), (0,3), (1,2), (2,3). Can it be done? By hand: put 0 on team red. Then 1 and 3 must be blue. Then 2, who dislikes 1, must be red. Check 2–3: red and blue, fine. It works. Now add one more refusal, (0,2). 0 and 2 are both red. Try again from scratch with 0 blue and the same clash appears. The triangle 0–1–2 can never be split into two teams, because three people in a circle cannot alternate two colours.
By hand you re-tried from scratch. With thousands of students and refusals, you want one pass that either produces the two teams or points at the clash.
Build the structure, one piece at a time
Piece one: the graph, as a list of neighbours per student: 0: [1, 3], 1: [0, 2], 2: [1, 3], 3: [0, 2].
Piece two: a colour array, one slot per student, starting empty.
Piece three: breadth-first search with one extra rule. Paint the start student with colour A and put them in a queue. Take a student out; for each neighbour: if unpainted, paint it the opposite colour and enqueue; if already painted, check it is the opposite colour; if it is the same colour, stop: the graph is not two-colourable.
| step | took out | colours (0,1,2,3) | queue |
|---|---|---|---|
| start | A, –, –, – | [0] | |
| 1 | 0 | A, B, –, B | [1, 3] |
| 2 | 1 | A, B, A, B | [3, 2] |
| 3 | 3 | A, B, A, B (2 is A, 3 is B, fine) | [2] |
Repeat from any unpainted student, since the graph may be in several pieces. With the extra edge 0–2, step 2 would find 2 already painted A while painting from 1, which is B, so 2 becomes A, and then 0–2 compares A with A: clash.
Why it is correct
The invariant: every edge whose both ends are painted joins two different colours. Painting a neighbour the opposite colour keeps it true; checking an already-painted neighbour keeps it true or reports a clash. If the search finishes with no clash, the colours are the two teams.
If there is a clash, why can no other painting succeed? Because in a connected piece the first colour forces every other colour: a neighbour must be opposite, its neighbour opposite again, and so on. There are only two possible paintings, mirror images of each other, and the clash appears in both. A clash means an odd cycle: going round a cycle alternates colours, so a cycle returns to its own colour only if its length is odd.
Why it is fast
Each student is painted and dequeued once, and each refusal is checked twice, once from each end:
work = V + 2E
Re-trying from scratch for each start, as the by-hand attempt did, would multiply this by V.
How to recognise it in an interview
Cues: "split into two groups", "no two neighbours in the same group", "is the graph bipartite", "dislikes" or "conflicts" as edges. The first thing to say: "two-colour it with BFS; a same-colour edge means an odd cycle and the answer is no." Is Graph Bipartite? is the routine itself. Possible Bipartition gives the dislikes as pairs; build the neighbour lists and run the same painting.
02The idea in one line
BFS/DFS painting neighbours the opposite colour; a clash means odd cycle.
Reach for it when: Is graph bipartite, possible bipartition, two-group splits.
Cost: O(V + E) time.
03The walk-through, step by step
The video works one example: Is Graph Bipartite? on a 4-node square plus a chord. These are its captions in order, so you can follow without the video or check a step you missed.
- Paint node 0 purple and BFS; every neighbour gets the opposite colour
- Pop 0: check each neighbour of 0
- 1 is unpainted: give it the opposite colour of 0
- 3 is unpainted: give it the opposite colour of 0
- 2 is unpainted: give it the opposite colour of 0
- Pop 1: check each neighbour of 1
- Edge 1–0: colours already differ, fine
- Edge 1–2: same colour on both ends, an odd cycle
- Not bipartite: the triangle 0-1-2 cannot be 2-coloured
- One BFS over the graph: O(V + E)
04Asked at Google
3 Google-tagged LeetCode problems use this pattern. Frequency is LeetCode's Google-tag score (higher means reported more often); "last 6 months" marks problems reported in the most recent window of the export.
| Problem | Difficulty | Frequency | Reported |
|---|---|---|---|
| Is Graph Bipartite? | Medium | 27 | last 6 months |
| Possible Bipartition | Medium | 11 | |
| Divide Nodes Into the Maximum Number of Groups | Hard | 11 |
05Related patterns
Other patterns in Graphs: Grid flood fill (components), Multi-source BFS, BFS shortest path (unweighted), BFS over an augmented state, 0-1 BFS (deque), DFS three-colour cycle detection, Topological sort (Kahn's), Union–Find (disjoint sets), Dijkstra (weighted shortest path), Bellman–Ford with k rounds, Minimum spanning tree, Eulerian path (Hierholzer), Bridges / articulation (low-link), Clone / traverse with a visited map, Implicit graph (states as nodes).