1
Two sides, edges only between
No edge within a side. The sides are independent sets, and the graph is exactly a relation between two populations.
Lesson · Graphs and Trees · Structure
Bipartite Graphs
A bipartite graph splits into two independent sets with every edge crossing between them. That is exactly the graphs with no odd cycle, and the equivalence is proved by a colouring argument.
bipartite: V = X ∪ Y disjoint, every edge crosses X–Y
bipartite ⟺ 2-colourable ⟺ NO ODD CYCLE
testable in one breadth-first search
K_{m,n} is bipartite; any odd cycle is not
Three equivalent descriptions
Core ideas
What this lesson establishes
Three characterisations of one class, and the third is what makes the class easy to test for.
2
Odd cycles are the only obstruction
A graph is bipartite exactly when every cycle has even length. Nothing else can prevent it.
3
The test is one search
Two-colour greedily by breadth-first search; a conflict is an odd cycle. Linear time, unlike almost every other question in this course.
The material
Bipartite graphs
Definition, the odd-cycle theorem, the test, and the applications.
Definition · Bipartite
A graph is bipartite when its vertices can be partitioned into sets X and Y such that every edge joins a vertex of X to one of Y. Equivalently, X and Y are independent sets.
Example · Bipartite and not
C₄, C₆ and every tree are bipartite. C₃, C₅ and Kₙ for n ≥ 3 are not. The complete bipartite graph K_{m,n} is bipartite by construction and has mn edges.
Theorem · The odd-cycle characterisation
A graph is bipartite if and only if it contains no cycle of odd length.
(⟹) Suppose the graph is bipartite and consider any cycle. Each step crosses from one side to the other, so after an odd number of steps you are on the opposite side from where you started. A cycle returns to its start, so its length must be even.
(⟸) Suppose there is no odd cycle. Work within one component; pick a vertex r and put each vertex in X or Y according to whether its distance from r is even or odd.
If some edge joined two vertices of the same class, the two paths from r to its ends, together with that edge, would give a closed walk of odd length, and a closed walk of odd length contains an odd cycle. So no such edge exists and the partition works. Repeat for each component.
□
The second direction is the substantive one, and the construction it uses is exactly the algorithm: colour by parity of distance from a root. The proof and the test are the same thing.
Theorem · The test
Breadth-first search from each unvisited vertex, colouring each vertex opposite to its parent. If an edge is ever found joining two vertices of the same colour, the graph is not bipartite and that edge closes an odd cycle. Otherwise the colouring is a bipartition. The cost is Θ(n + |E|).
Contrast that with “Graph Colouring”'s chromatic number, where deciding 3-colourability is NP-complete. Two colours is easy and three is hard, and the boundary is exactly here.
Matching
Definition · Matching
A matching is a set of edges no two of which share a vertex. In a bipartite graph, a matching pairs up members of X with members of Y.
Theorem · Hall's marriage theorem
A bipartite graph with parts X and Y has a matching saturating X if and only if every subset S ⊆ X has at least |S| neighbours in Y.
The condition is obviously necessary — |S| vertices need |S| distinct partners — and the content of the theorem is that it is sufficient. Note the resemblance to the pigeonhole principle: if some set of k vertices has fewer than k neighbours, two of them must share, and no matching exists.
Where bipartite graphs appear
- Assignment problems. Workers and jobs, students and projects, applicants and posts — anything pairing two populations.
- Scheduling. Rooms and time slots.
- Recommendation. Users and items, with edges for interactions.
- Testing for structure. Bipartiteness is a cheap and informative property, and its failure exhibits an odd cycle.
Interactive
Graph workbench
Your graph, the course's algorithms
Method
Testing bipartiteness
Colour by breadth-first search; a conflict is the proof it fails.
1
Pick an unvisited vertex and colour it
Say colour 0. Any starting choice works; the two colourings differ by swapping.
2
Colour each neighbour the opposite colour
Proceeding by breadth-first search, so each vertex is coloured when first reached.
3
Check every edge
An edge joining two vertices of the same colour means no bipartition exists, and it closes an odd cycle.
4
Repeat for every component
Each component is coloured independently. A disconnected graph is bipartite exactly when all its components are.
Bipartite
Score 0 / 0Choose the answer you can justify.
Two cycles
C₆ and C₅, coloured by distance parity from vertex 1.
C₆: 1–2–3–4–5–6–1
distance from 1: 0 1 2 3 2 1
colours: X Y X Y X Y
every edge crosses X–Y BIPARTITE
X = {1,3,5} Y = {2,4,6}
C₅: 1–2–3–4–5–1
distance from 1: 0 1 2 2 1
colours: X Y X X Y
the edge 3–4 joins two X vertices NOT BIPARTITE
That edge closes the odd cycle 1–2–3–4–5–1, of length 5.
The failing edge is not an accident of the colouring order: any attempt produces a conflict somewhere, because the obstruction is the odd cycle and it is present regardless of where the search starts.
Common mistakes
1
Assuming triangle-free means bipartiteC₅ has no triangle and is not bipartite. Every odd cycle is an obstruction, not only the shortest one.
2
Testing only one componentA disconnected graph is bipartite exactly when every component is. Each needs its own colouring.
3
Reporting failure without the odd cycleThe conflicting edge closes one, and naming it turns "not bipartite" into a proof.
Check your understanding
✓
Finish when you can produce the odd cycle from a failed colouring.
Two-colour a graph of your own until it fails, then trace the paths from the root to both ends of the offending edge. Together with the edge they form the odd cycle.
Note: The gap between 2-colouring and 3-colouring is one of the sharpest in complexity theory: the first is linear time and the second is NP-complete. “Graph Colouring” returns to it, and Algorithms and Complexity explains what NP-complete means.