BTT Mathematics / Primary Mathematics Learning Hub / Graph Matchings
A matching in a graph is a collection of edges that do not share endpoints. In an assignment problem, this means one person, task or resource cannot be used twice inside the same matching.
A bipartite graph separates vertices into two groups, such as pupils and projects, with edges showing which pairings are allowed. The central question is often whether every vertex on one side can receive a distinct compatible partner.
This guide is Primary Mathematics enrichment. It connects Route Networks, Graph Coloring, Multiple Constraints and Optimisation.
Formal matching theorems are optional extension. The practice uses small finite graphs where feasibility and impossibility can be justified directly.
Matching basics · Bipartite assignments · Perfect matchings · Bottlenecks · Improving a matching · 24 questions · Worked answers
1. Matching edges cannot share endpoints
Suppose A can pair with X and Y, and B can pair with Y. The edges A-X and B-Y form a matching. Edges A-X and A-Y do not, because A would be used twice.
Worked example A: Maximum size
With three vertices on the left and two on the right, no matching can contain more than 2 edges, because each edge uses a different right-side vertex.
Worked example B: Empty matching
The collection with no edges is technically a matching of size0.
Worked example C: Maximal versus maximum
A matching is maximal if no more edge can be added without conflict. It is maximum if no larger matching exists anywhere in the graph. A maximal matching need not be maximum.
Worked example D: Pairing interpretation
Matching edges represent simultaneous assignments. Unmatched vertices remain unassigned.
2. Bipartite graphs model two different types of object
Let pupils be P1,P2,P3 and projects be A,B,C. An edge means that pupil may take that project.
Worked example E
P1→A,B; P2→B,C; P3→A,C. One full assignment is P1-A, P2-B, P3-C.
Worked example F: Another valid assignment
P1-B, P2-C, P3-A is also valid.
Worked example G: Compatibility matters
A three-person/three-project system does not automatically have a full matching. Missing compatibility edges may prevent it.
Worked example H: Degree zero
If P3 has no edges, P3 cannot be matched under any assignment. A perfect assignment is impossible immediately.
3. A perfect matching covers every vertex in the intended set
When the two sides have equal size, a perfect matching commonly means every vertex on both sides is matched exactly once.
Worked example I: Complete 3-by-3 compatibility
If every pupil is compatible with every project, a perfect matching certainly exists. There are multiple possible assignments.
Worked example J: Forced edge
If P1 is compatible only with A, then every perfect matching must include P1-A.
Worked example K: Propagation
After assigning P1-A, remove A from the candidate sets of all other pupils. This can force further choices, just like constraint propagation in Latin-square problems.
Worked example L: Unbalanced sides
If four pupils compete for only three single-use projects, all four cannot be matched simultaneously. The right side gives an immediate capacity bound of3.
4. Small neighborhoods can prove impossibility
A bottleneck occurs when a group of left-side vertices collectively has too few available right-side neighbors.
Worked example M: Two pupils, one shared project
If P1 and P2 are both compatible only with A, they cannot both be assigned distinct projects. Two pupils have only one available neighbor.
Worked example N: Three pupils, two possible projects
If P1,P2,P3 are collectively connected only to A and B, then at most two can be matched. A full three-person assignment is impossible.
Worked example O: Exact fit
If a group of three pupils has exactly three available projects, a full assignment may be possible, but it is not guaranteed merely by the count. The internal compatibility pattern still matters.
Worked example P: Counting lower information
“Four pupils, four projects” gives capacity but not feasibility. Matching problems depend on who can pair with whom.
5. An alternating path can improve a matching
Sometimes an unmatched vertex can be accommodated by rearranging earlier assignments rather than abandoning them.
Worked example Q
Suppose P1-A is currently matched. P2 can use only A, while P1 can also use B. Reassign P1 from A to B, then assign P2-A. Matching size increases from1 to2.
Worked example R: Alternating structure
The change follows an alternating path: unmatched edge P2-A, matched edge A-P1, unmatched edge P1-B. Flipping matched/unmatched status along the path increases the matching by one.
Worked example S: Local greed can fail
Assigning a flexible pupil to the only project available to another pupil may block a complete matching. Good assignment order often protects scarce options.
Worked example T: Maximum proof
If a matching uses all three projects in a graph with only three right-side vertices, its size3 is maximum automatically; no matching can use four distinct right endpoints.
6. Practice: 24 original questions
Questions 1–8: Matching basics
1. May two edges in one matching share a vertex?
2. What is the size of a matching containing three edges?
3. With five left vertices and two right vertices, what is the largest possible matching size?
4. Is the empty edge set a matching?
5. Distinguish maximal from maximum.
6. Why can A-X and A-Y not both belong to one matching?
7. If every right-side vertex is already used, can another matching edge be added?
8. What does an unmatched left-side vertex represent in an assignment model?
Questions 9–16: Bipartite assignment and bottlenecks
9. P1→A,B; P2→B,C; P3→A,C. Give one perfect matching.
10. Give a different perfect matching.
11. If P3 has no compatible project, can a perfect matching exist?
12. If four pupils have only three single-use projects, can all four be matched?
13. P1 and P2 are compatible only with A. Can both be matched?
14. Three pupils collectively have only two available projects. What is the maximum number of them that can be matched?
15. If P1 is compatible only with A, what edge must every perfect matching contain?
16. After assigning P1-A, what should happen to A in other pupils’ candidate sets?
Questions 17–24: Rearrangement and proof
17. Current matching P1-A; P2 only uses A; P1 can also use B. How can size2 be achieved?
18. What is an augmenting path used for?
19. Why can a greedy first assignment block a later full matching?
20. A graph has three right-side vertices and a matching of size3. Can a larger matching exist?
21. Does equal side size alone guarantee a perfect matching?
22. What kind of subset provides an immediate impossibility certificate when it has fewer available neighbors than vertices?
23. If every vertex on both sides of a 4-by-4 bipartite graph is matched exactly once, what is the matching size?
24. Explain why a maximum matching is always maximal but a maximal matching need not be maximum.
7. Worked answers
Answers 1–8
1. No.
2. 3.
3. 2.
4. Yes.
5. Maximal means no edge can be added to that matching; maximum means no larger matching exists in the graph.
6. Vertex A would be used twice.
7. No.
8. An unassigned person/task/resource.
Answers 9–16
9. P1-A, P2-B, P3-C.
10. P1-B, P2-C, P3-A.
11. No.
12. No.
13. No.
14. At most2.
15. P1-A.
16. Remove A from them.
Answers 17–24
17. Reassign P1-B, then match P2-A.
18. To rearrange matched and unmatched edges so the matching size increases by one.
19. A flexible vertex may consume a scarce partner needed by a less flexible vertex.
20. No. Three right-side vertices cap matching size at3.
21. No. Compatibility structure may still block a full assignment.
22. A bottleneck subset.
23. 4.
24. If a matching is maximum, no larger one exists, so no single edge can extend it. A maximal matching can be locally stuck while a different rearranged matching is larger.
8. Teaching and transfer
If a learner treats matching as ordinary counting, draw the endpoints. Every selected edge consumes both endpoints and changes what remains possible.
When a perfect matching is assumed from equal totals
Look for a bottleneck subset. Capacity must exist locally, not only globally.
When an early choice blocks the puzzle
Protect forced or scarce options first. Flexible vertices can often be rerouted later.
When rearrangement feels like “changing the answer”
Emphasize that the goal is a simultaneous compatible assignment. Earlier tentative choices are not sacred; they can be rerouted if constraints remain satisfied.
When maximal and maximum are confused
Use a small counterexample where no extra edge can be added directly, yet swapping one chosen edge allows two new edges and creates a larger matching.
Connect to constraints
Matching is a candidate-allocation problem. The same elimination habits used in Latin Squares and Sudoku Structure help reveal forced assignments and bottlenecks.
Continue through this enrichment collection
For stochastic state movement, use Random Walks, Transition Probabilities and Markov Chains. For topological diagrams, use Knot Theory, Links, Crossings and Simple Invariants. For counting decompositions, use Integer Partitions, Ferrers Diagrams and Counting Structures.
Return to the BTT Primary Mathematics Learning Hub.
Original enrichment guide with 24 original practice questions and separate worked answers. Matching claims concern finite simple bipartite examples defined locally.