Find maximum-cardinality bipartite matchings and diagnose shared shortages.
By the end: separate feasible, maximal, maximum, and preference-aware assignments.
A bipartite graph divides vertices into two disjoint sets with every edge crossing between them. Here A, B, C are workers and D, E, F are jobs. An edge means that worker is eligible for that job. A matching selects edges with no repeated endpoint, so each worker and each job is used at most once.
A maximum-cardinality matching selects as many pairs as possible. A maximal matching merely cannot accept another edge without removing an existing selection. A poor early choice can make a matching maximal but smaller than the maximum. A perfect matching covers every vertex on both sides; unequal side sizes rule that out.
A compatibility graph records possibilities, not commitments. A worker may have several eligible jobs, and a job may have several eligible workers. Selecting an edge commits both endpoints for this one assignment round. The graph itself can have many edges touching A; the matching can select at most one of them. This is why counting eligibility edges does not count completed assignments. It also explains why drawing workers on one side and jobs on the other is useful. Every chosen edge must use one object of each kind, with neither object already committed elsewhere.
Use a six-vertex paper graph with workers A, B, C and jobs D, E, F. Its only eligibility edges are A-D, A-E, B-D, B-E, C-D. All workers have at least one option. Nevertheless, no edge reaches F, and every assignment must use either D or E. A-D together with B-E gives two pairs and leaves C unassigned. Adding C-D would double book D. Replacing A-D with C-D keeps two pairs rather than increasing the total. Two is the maximum because there are only two jobs incident to any eligibility edge.
Feasibility and optimality require different checks. To check a proposed matching, confirm that each selected pair exists in the original edge set and that no endpoint appears twice. The proposed pairs A-F and B-E have distinct endpoints, but A-F is absent and therefore ineligible. The proposed pairs A-D and C-D both exist, but repeat D and therefore conflict. A-D and B-E pass both tests. Neither test alone proves that two is the best possible count. That conclusion needs an upper bound or a procedure that rules out all larger feasible selections.
A matching's cardinality means its number of selected edges, hence its number of completed pairs. Every pair uses one worker, so cardinality cannot exceed the worker count. It also cannot exceed the job count. For three workers and three jobs, three is an absolute upper bound, but the previous paper graph has the stronger bound two. Having equally many vertices on both sides is necessary for a perfect matching, yet it does not ensure one exists. Compatibility can concentrate many options on the same few jobs while leaving other jobs inaccessible.
The one-use rule depends on what a vertex represents. A vertex labeled Nurse A might mean a whole day's assignment or one particular shift. If the same person may fill both morning and evening shifts, one vertex with a one-use constraint would forbid that. Splitting the person into two shift-specific vertices could permit both, but then rest rules or overlapping hours may require extra constraints. Likewise, one job vertex means one available slot here. Several identical openings cannot be inferred from several incoming edges, because those edges describe alternative workers for the same single opening.
| Proposed selection | All pairs eligible? | Endpoints distinct? | Conclusion |
|---|---|---|---|
| AF, BE | No: AF absent | Yes | Infeasible |
| AD, CD | Yes | No: D repeated | Infeasible |
| AD, BE | Yes | Yes | Feasible, size 2 |
Adding an eligible edge can never reduce the mathematical maximum, since every previous matching remains available. It may leave that maximum unchanged. In the paper graph, adding C-E still leaves all workers competing for D and E, so the maximum stays two. Adding C-F instead allows A-D, B-E, C-F and reaches three. Both changes give C another option, but only one reaches an additional usable job. This comparison shows why local degree is not enough to evaluate an assignment proposal. The relevant question concerns distinct endpoints available across the whole competing group.
In the example, A can do D or E, while B can do only D. Assigning A-D first blocks B. Reassigning A to E frees D for B and increases the total. This is an alternating path: unselected and selected edges alternate. Flipping the choices along a path with unmatched endpoints increases matching size by one.
The problem also reduces to maximum flow. Add a source with capacity-one edges to workers, orient eligibility edges toward jobs with capacity one, and connect each job to a sink with capacity one. Integral flows enforce single use. Our six-vertex visualizer enumerates subsets exactly instead of pretending to demonstrate a scalable matching implementation.
An alternating path switches between edges outside a matching and edges inside it. To increase the number of pairs, start at an unmatched worker, finish at an unmatched job, and alternate in that order. Such a path is called augmenting. Its endpoints acquire partners; every internal vertex exchanges one selected edge for another. Because the path starts and ends with unselected edges, it has one more unselected edge than selected edges. Choosing the former and removing the latter increases cardinality by exactly one. Internal vertices remain used once, so the exchange preserves feasibility.
Consider the first interactive preset's exact graph. Workers are A, B, C, jobs are D, E, F, and edge records are A-D, A-E, B-D, C-E, C-F in that order. The greedy selection accepts A-D, rejects A-E and B-D because they conflict, then accepts C-E and rejects C-F. This produces two pairs. B and F are unmatched, but no B-F eligibility edge exists. No edge can simply be added. The selection is maximal, even though the graph permits a larger matching. Being unable to add directly does not rule out a chain of replacements.
Start at B and inspect its only edge to D. D is currently paired with A, so accommodating B requires moving A. A has the alternative job E, currently paired with C. C has the alternative job F, which is free. The vertex sequence B, D, A, E, C, F uses only the listed eligibility edges and repeats no vertex. Its edge statuses are unselected, selected, unselected, selected, unselected. The chain ends at a free job rather than at another worker who would remain displaced. That endpoint is what makes an extra completed pair possible.
Flip all five decisions together. Remove A-D and C-E, then select B-D, A-E, and C-F. The resulting three pairs have six different endpoints. Every selected pair was eligible before the change; the exchange adds no compatibility. Only the commitments change. It is best understood as a proposed replacement allocation, not as an instruction to double book during a transition. A real staffing process might require consent or a coordinated handover. Those operational constraints are absent from the matching graph, whose task is to compare the original feasible selection with the new feasible selection.
The endpoint-count argument generalizes beyond this example. Along any such path, each internal worker loses one job and gains one; each internal job loses one worker and gains one. The formerly unmatched endpoints each gain one selected edge. This leaves no repeated endpoint. Merely alternating along a closed cycle would not increase cardinality because it removes and adds equal numbers of edges. Likewise, a chain ending at an already occupied job without continuing through its selected edge is incomplete. It proposes a conflict rather than an augmenting path, even if most of the chain alternates correctly.
There is also a reason augmenting paths are sufficient for finding a maximum. Compare a current matching with any larger matching, retaining only edges chosen by one but not both. At every vertex, at most two retained edges meet, one from each matching. The retained pieces are alternating paths or alternating cycles. Cycles contain equal numbers from each selection. If the second selection is larger overall, some path must contain one extra edge from it. That piece is an augmenting path for the current selection. The widget instead checks subsets exhaustively, but this argument explains why reassignment algorithms can work.
2 pairs: A–D, C–E.
3 pairs: A–E, B–D, C–F.
| Edge | Eligibility record |
|---|---|
| A–D | Eligible, not selected |
| A–E | Selected in maximum |
| B–D | Selected in maximum |
| C–E | Eligible, not selected |
| C–F | Selected in maximum |
| Worker | Chosen eligible job |
|---|---|
| A | E |
| B | D |
| C | F |
The two panels deliberately answer different questions. The greedy reference visits eligibility records in their displayed order and accepts a pair whenever both endpoints remain unused. It never retracts a choice. The maximum panel considers possible subsets of those records and keeps a largest feasible subset. On Reassignment fills three jobs, the two-panel comparison should therefore show two pairs against three, not two equally good procedures with different artwork. The five-edge chain above explains the gap. The graph has not changed between the panels, and no job has gained extra capacity in the second panel.
To see what exhaustive search means, imagine making a yes-or-no choice for each of the five eligibility records. There are two choices for the first record, two for the next, and so on, yielding thirty-two subsets before any conflicts are rejected. Some contain no pairs, some contain repeated endpoints, and some are feasible matchings. Keeping a largest feasible one proves maximum cardinality for this small graph because no possible selected edge set was omitted. The implementation can stop exploring conflicting choices early. Thirty-two describes the full set of candidates, not measured runtime or necessarily the number of complete subsets it visits.
| Candidate subset | Endpoint check | Feasible size |
|---|---|---|
| Empty set | No repeated endpoint | 0 |
| AD | No repeated endpoint | 1 |
| AD, AE | A repeated | Not feasible |
| AD, CE | No repeated endpoint | 2 |
| AE, BD, CF | No repeated endpoint | 3 |
The include-or-exclude order also affects which optimum appears when several have the same size. This model tries including a currently available edge before excluding it and replaces its saved result only when cardinality strictly increases. Thus the first maximum it finds remains displayed. That is a deterministic selection rule, not a preference score or a fairness policy. In a graph with two different three-pair matchings, either would certify the same maximum count. To explain why one human allocation is preferable, the model would need information beyond the eligibility relation and the objective of completing as many pairs as possible.
Choose Shared shortage at D next. Its only edges are A-D, B-D, C-E, C-F. Greedy accepts A-D and C-E for two pairs. Exhaustive search cannot improve that count, because A and B both need D and only one can receive it. C can use E or F, but that flexibility does not provide a second job for A and B. A matching of two is attainable and three is impossible. The two panels now agree for a reason grounded in the eligibility constraints, rather than because the greedy procedure has acquired a general optimality guarantee.
Choose Maximal is not maximum. Only A-D, A-E, and B-D remain; C and F are still present as isolated vertices. Greedy keeps A-D and stops with one pair. The maximum selection A-E and B-D has two. It cannot reach three because C has no eligible job, and F has no eligible worker. This preset separates three ideas that are easy to merge: the two sides have equal size, reassignment can improve a poor selection, and a perfect matching may still be impossible. Reassignment does not repair an absent edge; it only uses alternatives that already exist.
| Records in order | Greedy | Maximum example | Upper bound |
|---|---|---|---|
| AD, AE, BD, CE, CF | AD, CE: 2 | AE, BD, CF: 3 | 3 workers |
| AD, BD, CE, CF | AD, CE: 2 | AD, CE: 2 | A and B share only D |
| AD, AE, BD | AD: 1 | AE, BD: 2 | Only A and B have edges |
Across these presets, use both the selected edge sets and the unmatched endpoints to explain each result. The candidate spaces have thirty-two, sixteen, and eight subsets respectively, because the graphs have five, four, and three eligibility records. Those small counts make exhaustive reasoning practical here. For a much larger graph, adding one more edge doubles the unconstrained subset count, so this method is not a claim about scalable assignment software. Efficient matching algorithms use additional structure such as augmenting paths. The existing widget illustrates exact bounded optimization and its contrast with irrevocable greedy choices, not the performance of those larger algorithms.
A complete assignment of all workers requires every subset of workers to have at least as many distinct eligible jobs as workers in that subset. This is Hall's condition, which is also sufficient in a finite bipartite graph. If two workers can both do only one shared job, each has a neighbor but they cannot both be assigned.
Cardinality alone does not encode preferences, skill scores, pay, fairness, or stability against mutually preferred reassignment. Those require different objectives or constraints. Compatibility edges may also be uncertain. A maximum matching proves an optimum for the stated graph, not that the resulting human allocation is desirable.
For a group of workers, its neighborhood means the set of distinct jobs eligible for at least one member. Count each job once, even when several workers can do it. Return to the paper graph with edges A-D, A-E, B-D, B-E, C-D and no others. The group {A, B} has neighborhood {D, E}, so two jobs are enough for those two workers considered alone. The whole group {A, B, C} still has neighborhood {D, E}. Three workers cannot receive distinct jobs from a set containing only two jobs, regardless of their individual degrees.
Hall's condition asks for enough distinct neighbors for every worker subset. For three workers there are seven nonempty subsets to consider: three individuals, three pairs, and the whole group. In this paper graph every individual has an option, and every pair has at least two jobs. Only the three-worker group fails. This makes the condition stronger than checking isolated workers or pairs. The finite bipartite theorem says the condition is also sufficient for assigning every worker. The empty subset adds no restriction because it needs zero jobs. Covering every worker need not cover every job when the two sides differ in size.
| Worker subset | Distinct jobs | Jobs versus workers |
|---|---|---|
| {A} | {D, E} | 2 ≥ 1 |
| {B} | {D, E} | 2 ≥ 1 |
| {C} | {D} | 1 ≥ 1 |
| {A, B} | {D, E} | 2 ≥ 2 |
| {A, C} | {D, E} | 2 ≥ 2 |
| {B, C} | {D, E} | 2 ≥ 2 |
| {A, B, C} | {D, E} | 2 < 3: shortage |
A deficient group gives a numerical bound as well as a yes-or-no obstruction. If three workers collectively reach only two jobs, at least one of them must remain unmatched. If E were removed from this paper graph while every other vertex remained, all three workers would reach only D. At least two workers would then remain unmatched, and a single eligible pair would attain the bound. Subtracting distinct available jobs from competing workers measures the forced shortage. The original two-pair construction and three-worker obstruction together prove its optimum. A failed Hall condition identifies where extra eligibility is needed rather than merely reporting that a search failed.
Add C-F to that paper graph. Now C can take F while A and B take D and E, so A-D, B-E, C-F constructs a complete assignment. Adding C-E instead would not help: the whole group would still reach only D and E. The repair must enlarge the neighborhood of the deficient group or reduce the number of workers requiring assignment. Improving an already flexible worker's options outside the relevant competing group may leave another shortage unchanged. This is the matching version of checking the actual binding constraint rather than celebrating an increase in the total number of edges.
The link to flow can be seen without enlarging this lesson's vertex limit. Take workers A, B, jobs D, E, with eligibility A-D, A-E, B-E. Add vertex C as a source and F as a sink. Direct capacity-one edges from C to each worker, from workers to their eligible jobs, and from each job to F. These are seven edges on six vertices. Conservation forces any unit entering a worker to continue through one eligible pair. Unit source and sink edges prevent double use. An integer flow of two corresponds to pairs A-D and B-E, covering both workers and jobs.
Neither a Hall certificate nor that flow construction ranks the resulting assignments by human desirability. For workers A, B, C and jobs D, E, F, let eligibility instead be A-D, A-E, B-D, B-E, C-F. Both A-D, B-E, C-F and A-E, B-D, C-F have maximum count three. The graph supplies no reason to prefer either. Preferences, compensation, or restrictions on who may be left unmatched require a stated additional objective or rule. The selected references establish mathematical compatibility and cardinality claims. They do not validate eligibility data, establish fairness, or show that any proposed real assignment can be implemented without negotiation.
Edges are A-D, A-E, and B-D. Why is {A-D} maximal but not maximum?
Try adding an edge without changing it, then try replacing it.
| Selection | Size | Can add directly? |
|---|---|---|
| A-D | 1 | No |
| A-E and B-D | 2 | No |
Neither remaining edge can simply be added: A-E repeats A and B-D repeats D. So {A-D} is maximal. Replacing it with {A-E, B-D} gives two disjoint pairs, so it is not maximum.
Three workers each have at least one eligible job. A and B can do only D; C can do E or F. Can all three workers be assigned?
Inspect the subset {A, B}.
| Worker subset | Distinct eligible jobs | Comparison |
|---|---|---|
| A, B | D | 1 job < 2 workers |
| C | E, F | 2 jobs ≥ 1 worker |
No. {A, B} has only the single distinct neighbor D, violating Hall's condition. At most one of A and B can work, plus C, so the maximum is two. Adding more options for C alone does not resolve the shortage shared by A and B.
Selected reference passages support the definitions and algorithms below. The networks, explanations, and implementations are original. Terminology and assumptions are stated within each lesson; source review is not an independent audit of this course. Optional links are not runtime dependencies.
Matching, maximum cardinality, perfect matching, alternating paths, and the flow reduction. Our small visualizer uses exhaustive subset search instead.
Secondary reference for the finite bipartite subset-neighborhood condition and its necessity argument. Covering one specified side is distinguished from covering every vertex on both sides.
Brief overview and links to implementations. This page is explicitly incomplete; substantive residual and certificate details were checked in the linked implementation.