Definition · Matching, maximal, maximumA matching in a bipartite graph is a set of allowed pairs no two of which share a vertex. It is maximal if no further pair can be added to it, and maximum if no matching is larger. A matching is perfect on the left if every left vertex is in it.
The construction
- Add a source with an arc of capacity 1 to every left vertex.
- Add a sink with an arc of capacity 1 from every right vertex.
- For each allowed pair, add an arc of capacity 1 from the left vertex to the right one.
- Find a maximum flow. The pair arcs carrying flow are a maximum matching.
Theorem · The two maxima coincideIn the network above, the maximum flow value equals the size of a maximum matching, and a maximum matching can be read off any integer maximum flow as the set of pair arcs carrying one unit.
A matching gives a flow of the same value, by routing one unit through each matched pair. The capacity 1 on the source arcs and the sink arcs is respected because a matching uses each vertex at most once, and conservation holds at every left and right vertex by construction.
An integer flow of value k gives a matching of size k. Each pair arc carries 0 or 1. If two pair arcs carrying flow shared a left vertex, that vertex would emit 2 while receiving at most 1, breaking conservation; the same argument on the right settles the other side. So the arcs carrying flow form a matching, and there are k of them because k units leave the source along distinct arcs.
Each maximum therefore bounds the other, so they are equal. The augmenting-path method returns an integer flow on this network because every capacity is 1 and every bottleneck is therefore 1.
□
Example · Three on the left competing for twoThe lab opens on three left vertices and two right ones with the allowed pairs L1–R1, L2–R1, L3–R1 and L3–R2. The network has 7 vertices and 9 arcs, and the maximum flow is 2, reached in two augmentations. The matching is L1 with R1 and L3 with R2. The cut, read back, is the cover {L3, R1}, of size 2. A search over every subset of the four pairs, which knows nothing about flow, also returns 2.
Check the cover against the pairs: L1–R1 is covered by R1, L2–R1 by R1, L3–R1 by both, and L3–R2 by L3. Four pairs, two vertices, everything touched. And no single vertex could do it, because L1–R1 and L3–R2 share nothing — which is the matching bounding the cover from below.
Why the matching stopped at two
The left vertices 1 and 2 have only one right vertex between them: both are joined to R1 and nothing else. Two of them cannot both be matched into one, so no matching covers all three left vertices. The lab exhibits that set rather than describing it, reporting S = {L1, L2} with a neighbourhood of size 1 against a set of size 2.
That is the general shape of the obstruction: a set of left vertices whose combined neighbourhood is smaller than itself. Whenever the matching misses a left vertex, the cut hands one back. It is a proof that no better matching exists, in a form a reader can check by looking at four pairs rather than by trusting a flow.
The lab's star case is the same phenomenon at a larger scale: four on each side with the pairs L1–R1, L2–R1, L3–R1, L4–R1 and L4–R4. The maximum matching is 2, the cover is {L4, R1} of size 2, and the deficient set is {L1, L2, L3} with a neighbourhood of exactly one vertex. One popular right vertex is the whole story, and the cover names it.
Greedy is maximal, and the order decides how maximal
Example · Three pairs, two orders, two answersTake two vertices on each side with the pairs L2–R2, L1–R2 and L2–R1. Taking them greedily in that order gives one pair: L2–R2 is taken and it blocks both of the others. Taking the same three pairs in the order L1–R2, L2–R1, L2–R2 gives two. The maximum is 2, confirmed by the exhaustive search and by the flow, and the cover has size 2 as well.
So a matching nothing can be added to may be half the size of the largest one, and which happens depends only on the order the pairs were considered in. That is the same distinction “Augmenting Paths” drew between maximal and maximum flow, appearing here in its most concrete form — and the augmenting path is exactly what repairs it, because an augmenting path in this network alternates between unmatched and matched pairs and swaps them.
Where the matching is perfect there is nothing to exhibit. On three left and three right with six pairs the lab returns a matching of size 3, a cover of size 3, and a greedy pass that also finds 3; the network has 8 vertices and 12 arcs. The construction is unchanged, and the absence of a deficient set is the report.
Measured against proved, for the last time on this course. The exhaustive search over subsets of the pairs is refused above the size it states — seventeen pairs is declined rather than run slowly — so below that cap “this matching is maximum” is a fact about a complete list, and above it the claim rests on the flow and its cut. The equality of the matching and the cover is proved by the max-flow min-cut theorem and confirmed on every case the panel runs, which is the right division of labour: the enumeration catches a construction that is wrong, and the theorem covers the sizes the enumeration cannot reach.