Did you know that assigning people to jobs can be harder than simply choosing the first available person? Imagine three students signing up for three school projects. Each student can only join certain projects, and each project needs one student. A careless first choice could leave someone apparently without a place—even when a complete assignment actually exists. Bipartite matching gives us a mathematical way to find the assignments that work.
The core aim of bipartite matching mastery is to represent two groups using a graph, define eligible connections, construct a matching, distinguish maximal from maximum matchings, use augmenting paths to improve an assignment, and understand when a perfect matching is possible. Students should learn how to revise an early assignment without violating any one-to-one restrictions. This is not merely an exercise in drawing connections. It is a practical form of discrete mathematical reasoning.
This article continues eduKateSG’s Mathematics Mastery route from Graph Theory, Network Flow, Integer Programming and Linear Programming. The distinct goal here is to master one-to-one assignments, their limitations and the logic that makes an assignment complete or optimal.
What Is a Bipartite Graph?
A bipartite graph is a graph whose vertices can be divided into two disjoint groups so that every edge connects a vertex from one group to a vertex in the other. No edge joins two vertices belonging to the same group.
For example, one group may contain students, and the other may contain school projects. An edge between Student A and Project 1 means Student A is eligible or willing to take that project.
Not every ordinary graph is bipartite. A triangle, for example, cannot be divided into two groups without leaving an edge inside one group. In general, an undirected graph is bipartite if and only if it has no odd cycle.
A Matching Uses Connections Without Reusing Endpoints
A matching is a set of edges with no common vertices. If a student is assigned to Project 1, that student cannot simultaneously be assigned to Project 2 in a one-to-one matching. The chosen project is likewise unavailable for another student.
Students should distinguish all allowable edges from the smaller set of edges actually selected for a matching.
Worked Example: Three Students and Three Projects
Suppose three students A, B and C can take the following projects:
| Student | Eligible projects |
|---|---|
| A | 1 or 2 |
| B | 1 only |
| C | 2 or 3 |
A valid complete assignment is:
- B→1;
- A→2;
- C→3.
All three students have different projects, and every chosen connection is eligible. The matching therefore contains three edges.
Greedy Choices Can Get Stuck
Now imagine assigning A→1 first and C→2 next. Student B can take only Project 1, which is already occupied. No unassigned project is directly available to B.
It might look as if only two students can be assigned. But that conclusion is wrong. The first assignment needs to be rearranged.
This is a useful lesson in mathematical decision-making: an early choice can block a later choice even when a better overall arrangement exists.
An Augmenting Path Repairs the Assignment
Start from the unmatched student B. Follow the eligible edge B–1. Project 1 is currently matched to A, so follow that matched edge backward to A. A also has an eligible edge to Project 2, currently matched to C. C has an eligible edge to the free Project 3.
The alternating sequence is:
B–1–A–2–C–3.
The edges alternate between unmatched and matched edges, starting and ending at unmatched vertices. Flip which edges are selected along this path:
- Remove A→1 and choose B→1 instead.
- Remove C→2 and choose A→2 instead.
- Choose C→3.
The matching now has three edges instead of two. No student or project is used twice. This is the central idea of an augmenting path.
Why Augmenting Paths Increase the Matching Size
An augmenting path contains one more unmatched edge than matched edge. Reversing the matching status along the path removes some currently selected edges but adds exactly one more than it removes.
Therefore the size of the matching increases by one while the selected edges still share no endpoints.
A student who understands this argument knows why the algorithm works, rather than merely following a drawing convention.
Maximal and Maximum Matchings Are Different
A maximal matching is one to which no additional edge can simply be added while keeping the existing matched edges unchanged.
A maximum matching has as many matched edges as possible among all matchings in the graph.
In our student example, the first matching A→1 and C→2 is maximal: the only unmatched student B cannot be directly assigned to the only unmatched Project 3. But it is not maximum, because the augmenting path produces three matches.
This is one of the most important vocabulary distinctions in the topic.
A Perfect Matching Covers Every Vertex
A perfect matching matches every vertex of the bipartite graph. This requires the two groups to have the same number of vertices.
In a school assignment, the phrase “every student gets one project” may be the relevant requirement. If the project group has extra unused projects, the student-complete matching is not a perfect matching of the entire graph, even though the school assignment goal has been met.
Always check whether the question asks to match every vertex, every member of one group or simply as many pairs as possible.
Hall’s Marriage Theorem Gives a Powerful Feasibility Test
For a finite bipartite graph with left-side group L, Hall’s theorem says a matching covering every vertex of L exists if and only if every subset S of L has at least |S| neighbours in the other group.
Symbolically:
|N(S)|≥|S| for every S⊆L.
Here N(S) is the set of all right-side vertices connected to at least one member of S.
Worked Example: When a Complete Assignment Is Impossible
Suppose Students A and B are both eligible only for Project 1. Student C is eligible for Projects 2 and 3.
Consider the subset S={A,B}. It contains two students, but its set of eligible projects is N(S)={1}, containing only one project.
So:
|N(S)|=1<2=|S|.
It is impossible to assign both A and B different eligible projects. No rearrangement can overcome that shortage without changing eligibility or adding another project.
Hall’s Condition Is Stronger Than Counting Total Projects
Having three students and three projects does not guarantee a complete assignment. The problem is whether every subgroup of students collectively has access to enough distinct projects.
This is why checking total quantities alone can be misleading. The arrangement of connections matters.
Augmenting Paths Characterise Maximum Matchings
A fundamental theorem in matching theory, often called Berge’s lemma, states that a matching is maximum if and only if there is no augmenting path relative to that matching.
That gives an algorithmic stopping rule: continue searching for augmenting paths until none exists. Then the matching cannot be enlarged.
The mathematical power lies in the guarantee that this stopping condition certifies an optimal cardinality.
Bipartite Matching Can Become a Network Flow Problem
We can transform a bipartite assignment graph into a flow network:
Each unit of integral flow corresponds to one selected matching edge. Capacity 1 at both ends enforces one-to-one assignment.
Thus a maximum flow in this construction gives a maximum bipartite matching. For the flow mechanics, visit Network Flow.
Integer Flow Matters for Whole Assignments
In the standard network-flow model with integer capacities, an integer-valued maximum flow exists. That is precisely what we need when one student must be assigned to one project, rather than fractionally sharing a project in a purely numerical solution.
This special integrality property links matching to Integer Programming. It also illustrates why exploiting mathematical structure is often preferable to treating every assignment as a generic search problem.
Kőnig’s Theorem Connects Matchings and Vertex Covers
A vertex cover is a set of vertices that touches every edge in the graph.
For bipartite graphs, Kőnig’s theorem states that the size of a maximum matching equals the size of a minimum vertex cover.
This connects the problem of selecting independent pairs with the problem of selecting a smallest set of vertices that collectively touch every connection. It is another beautiful example of two apparently different optimisation questions sharing one mathematical answer.
Maximum Matching and Minimum-Cost Assignment Are Different
A maximum-cardinality matching asks to assign as many pairs as possible. But sometimes one assignment has a travel cost, workload or suitability score that differs from another.
In a weighted assignment problem, the goal might be to minimise total cost across a complete set of assignments, or maximise total suitability. This requires considering weights, not only the number of matches.
The Hungarian algorithm is a classical method for the assignment problem. Other weighted matching methods may also be appropriate depending on the structure.
Worked Example: Why Match Count Is Not Enough
Suppose two workers can both do either of two jobs. The time costs are:
| Worker / Job | Job X | Job Y |
|---|---|---|
| A | 2 hours | 7 hours |
| B | 6 hours | 3 hours |
Both full assignments match two workers to two jobs. But:
- A→X and B→Y cost 2+3=5 hours;
- A→Y and B→X cost 7+6=13 hours.
Both are maximum matchings by cardinality. Only the first is the minimum-cost complete assignment. The objective matters.
Applications to Schools and Workplaces
Matching models can support:
- students assigned to school projects or mentors;
- workers assigned to shifts or jobs;
- volunteers allocated to tasks they can perform;
- machines assigned to compatible work orders;
- applicants assigned to eligible opportunities;
- delivery teams assigned to locations.
The modelled edges must be grounded in genuine eligibility or availability information. Where real people are affected, fairness, preferences, constraints and safeguarding may require more than a simple one-to-one graph.
When a Simple Matching Model Is Not Enough
Some projects need several students. Some students can join multiple projects. Some assignments depend on time or workload limits. Those situations may require capacities, generalised matching, b-matching, scheduling or more elaborate optimisation models.
Choosing the right model is part of mathematics mastery. A beautifully solved one-to-one matching problem still gives the wrong operational decision if each project actually needs three people.
Common Bipartite Matching Mistakes
- Connecting vertices within the same partition when a bipartite structure is required.
- Assigning the same worker or project twice in a one-to-one matching.
- Stopping after a greedy assignment becomes stuck.
- Confusing maximal and maximum matchings.
- Calling a matching perfect when it does not cover every vertex.
- Assuming equal group sizes guarantee a perfect matching.
- Following an augmenting path without alternating matched and unmatched edges.
- Confusing maximum cardinality with minimum cost.
- Ignoring fairness, availability or capacity constraints in real applications.
Three Learning Pathways
Repair: Read the Two-Part Graph
Begin with three students and three tasks. Identify the two groups, list allowed edges, and draw a matching where no endpoint is used twice. Separate the idea of an eligible connection from an assigned connection.
Stabilise: Rearrange and Verify
Practise examples where a greedy choice gets stuck. Find alternating augmenting paths, flip the chosen edges and check that the matching size grows by one. Explain the distinction between maximal and maximum.
Extend: Theorems and Optimisation Connections
Study Hall’s condition, Berge’s lemma, maximum-flow reductions, vertex covers and weighted assignment problems. Compare one-to-one matching with capacity-constrained assignments.
A Weekly Bipartite Matching Routine
- Draw one small two-group eligibility graph.
- Construct an initial matching and check it for repeated endpoints.
- Find an augmenting path if one exists.
- Explain why flipping the path increases the number of pairs.
- Test a subgroup for a Hall-condition shortage.
- Compare maximum cardinality with minimum-cost assignment.
Parent and Student Progress Checklist
- I can define the two partitions of a bipartite graph.
- I know which edges are eligible.
- I can construct a valid matching.
- I distinguish maximal from maximum.
- I understand a perfect matching.
- I can find and use an augmenting path.
- I can explain why an augmenting path increases matching size.
- I understand Hall’s condition.
- I know how matching connects to network flow.
- I distinguish maximum matching from minimum-cost assignment.
- I can state assumptions that a practical assignment model must respect.
Frequently Asked Questions
What is bipartite matching in simple terms?
It is the task of pairing vertices from two groups along allowed edges without using the same vertex more than once.
What is the difference between maximal and maximum matching?
A maximal matching cannot be enlarged merely by adding an edge without changing existing matches. A maximum matching has the greatest possible number of edges overall.
What is an augmenting path?
It is an alternating path that begins and ends at unmatched vertices. Switching the matched and unmatched edges along it increases the matching size by one.
How does maximum flow help with matching?
Connect a source to left-side vertices, allowed pairs across the groups, and right-side vertices to a sink, all with unit capacities. A maximum integral flow then represents a maximum matching.
Helpful Reading in the eduKateSG Ecosystem
- Graph Theory
- Network Flow
- Integer Programming
- Linear Programming
- Graph Theory, Networks and Internet Routing
- Mathematics Learning Hub
The Core Aim
The core aim of bipartite matching mastery is not to make students draw more lines between two columns of names. It is to make constrained assignments logical, verifiable and repairable.
A strong learner can build the correct bipartite graph, find a matching, recognise when a greedy decision blocks progress, use an augmenting path to improve it, and explain whether the final assignment is as large as possible. That is what bipartite matching adds to mathematics mastery: a clear way to turn compatibility and limited opportunities into the best feasible pairing.