A matching is a flow. Put a unit arc from a source to every applicant, keep every original edge at capacity one, and put a unit arc from every job to a sink: a flow of value k is a matching of size k, and it comes out whole because of the matrix. Then the minimum cut is not just a bound — it names a set of applicants whose jobs between them are too few, which is Hall's condition failing, and it is a certificate anybody can check by counting.
Core ideas
The reduction is three lines and the integrality is already proved. What this lesson adds is that the failure comes with a reason attached.
Unit arcs from a source to the applicants, the original edges at capacity one, unit arcs from the jobs to a sink. Any integral flow of value k saturates k of the source arcs and k of the sink arcs and uses k edges no two of which share an endpoint — a matching. And the flow is integral because the constraint matrix is the one already swept for total unimodularity: half an applicant is excluded by the matrix, not by the algorithm.
If some set S of applicants has fewer jobs between them than there are members of S, clearly not all of S can be placed. That direction is counting. The content of the theorem is the converse, and the flow argument supplies it constructively: when the maximum matching falls short, the minimum cut produces the violating S.
The lab prints S, its neighbourhood N(S) and the difference. Verifying the claim means listing the jobs those applicants are willing to take and counting them — no algorithm, no trust. That is the same shape as a cut certifying a flow and a critical path certifying a project length, which by now is the point of the whole course.
The material
The reduction, then the theorem, then the three instances: one where every job is filled and somebody is still left out, one where the deficient set is small, and one where nothing is deficient.
In a bipartite graph with parts X and Y, a matching is a set of edges no two of which share a vertex. It saturates X when every member of X is in one of its edges.
For S ⊆ X, write N(S) for the set of vertices in Y joined to at least one member of S. Hall's condition is that |N(S)| ≥ |S| for every S ⊆ X.
A bipartite graph has a matching saturating X if and only if |N(S)| ≥ |S| for every subset S of X.
Discrete Mathematics states this in “Bipartite Graphs” and does not prove the sufficient direction. This lesson supplies it as a consequence of max-flow min-cut, and does so constructively: when the maximum matching misses a vertex, the minimum cut of the flow network exhibits the violating S.
The reduction is short enough to keep in your head. Add a source with a capacity-one arc to each member of X; keep every edge of the graph as an arc of capacity one; add a sink with a capacity-one arc from each member of Y. On a three-applicant, two-job instance that is seven nodes and eleven arcs.
Both jobs are filled, and an applicant is still left out. Those two sentences are not in tension: there are three applicants and two jobs, and a matching saturating the applicants would need three distinct jobs. The certificate is the whole of X here, and it takes one sentence to check — all three applicants will take only a or b, and there are two of those.
Edges 1-a, 2-a, 3-a, 4-b, 4-c, 4-d. The maximum matching has two edges out of a possible four, the minimum cut has capacity 2, and the deficient set the cut names is S = {1, 2, 3} with N(S) = {a}.
Three applicants, one job between them, a shortfall of two. Applicant 4 is not part of the certificate at all — it has three jobs to itself and is doing nothing wrong. A reader who expects the violating set to be all of X will not find it here, and the searching that follows is exactly what the minimum cut saves.
Edges 1-a, 1-b, 2-b, 2-c, 3-c, 3-d, 4-d, 4-a: four applicants in a ring with four jobs. The maximum matching has four edges, every applicant is placed, and the minimum cut has capacity 4 — the set {src} alone.
S and N(S) come back empty and the lab reports that Hall's condition holds on every subset. There is nothing to certify: the alternating search that produces the violating set starts from the unmatched applicants, and here there are none. Remove one edge and the certificate appears.
König's theorem — that in a bipartite graph the smallest vertex cover has exactly as many vertices as the largest matching — is the same statement again. The lab computes the cover from the matching, and it is the cover the Hungarian method was counting when it drew lines through the zeros. On the three-applicant instance the cover is the two jobs; on the three-sharing-one instance it is applicant 4 together with job a.
So the assignment lesson's cover step, this lesson's deficient set, and the maximum-flow theorem are three readings of one fact. That is not a coincidence worth admiring; it is the reason the assignment problem can be solved by a method with a stopping proof, and the reason that method's most delicate step is the one this lesson has now justified.
One limitation to state plainly. All of this is about bipartite graphs. Matching in a general graph is a genuinely harder problem with a different theory, its own theorem about odd sets, and an algorithm this path does not contain. The boundary is exactly the odd cycle that broke total unimodularity in the integrality lesson, which is a pleasing place for a course to end.
Interactive
When the matching falls short, the minimum cut hands you the set with too few neighbours
Method
Build the network, find the flow, and then take whichever of the two certificates the answer offers you.
Source to every applicant at capacity one, every edge at capacity one, every job to the sink at capacity one. Every capacity is one; a capacity of two anywhere means somebody is being allowed two jobs, and that is a different problem.
The arcs between the two sides carrying one unit are the matched pairs. The flow is whole automatically — this is a network, and its matrix is totally unimodular — so there is no rounding step and no half-matched applicant to interpret.
Equal, and everybody is placed. Short, and there is a certificate to produce, which is the interesting case and the one most write-ups skip.
S is the set of applicants on the source side of the minimum cut. Write it down with N(S), and check the count: |N(S)| < |S|. That inequality is the answer to “why can they not all be placed”, and it is checkable without re-running anything.
A saturating matching exists and you have one. Hall's condition holds on every subset, but you have not checked every subset and you do not need to: the matching itself is the certificate in this direction.
Each block is the maximum matching, the minimum cut of the flow network, and the deficient set the cut names. All of it is what the lab reports.
Graph 1 is the one that catches people. Every job is filled — the matching saturates the jobs perfectly — and an applicant is still left out, because saturating the applicants is a different requirement. The certificate is about the applicants, and it says the whole of X has only two jobs between it.
For a rehearsal, take graph 2 and add the edge 1-b. The matching goes to three and the certificate shrinks: the deficient set is now {2, 3} with a single job between them. Keep adding edges and watch the set contract until it disappears.
The harder rehearsal: take graph 3 and remove 4-a. Everybody is still placed, because the ring had slack in it. Remove 4-d as well and applicant 4 has nothing left; the certificate that appears is S = {4} with N(S) empty, which is the smallest violation there is.
You should be able to build the unit-capacity network from a bipartite graph, read a matching off a flow, explain why the flow is whole, produce the deficient set from the minimum cut when the matching falls short, check |N(S)| < |S| by counting, and say why a saturating matching needs no further certificate.
Something to change about this lesson? Write it down, tick it off when it is handled, and export the list when you want to act on it. Kept in this browser only: nothing is sent anywhere, and nobody is notified.
No recommendations yet for this lesson.