From assignments to a graph
Suppose each student can take at most one project and each project can accept at most one student. An edge records an allowed pairing. A large collection of allowed edges does not imply that everyone can be assigned: several students may depend on the same single project. We assume throughout a finite bipartite graph , with every edge joining a left vertex to a right vertex.
Definition 2.2.1
(Matching)
A matching in is a set of edges no two of which share an endpoint. A vertex is matched if some edge of meets it, and unmatched otherwise. A maximum matching is one of largest size .
Our goal is to maximize the size of a matching, not merely to find a matching to which no single edge can be added.
Common mistake
(Maximal is not maximum)
A matching to which no edge can be added is called maximal; it need not be maximum. For edges , the matching is maximal, since and both meet it, yet is larger. Greedy addition of edges stops at a maximal matching; reaching a maximum one may require undoing an earlier choice, as the first worked example shows.
Build a flow network
Add a source and sink . For each add with capacity one; for each edge add with capacity one; for each add with capacity one.
Proposition 2.2.2
(Maximum matchings are maximum integer flows)
In this network, the maximum flow value equals the maximum matching size of . More precisely, matchings correspond to integer feasible flows of the same value.
Proof
(Translate in both directions)
A matching gives a feasible integer flow by sending one unit along for each selected edge. Its flow value equals the matching size.
Conversely, take an integer feasible flow. Unit capacities make every edge flow zero or one. Conservation and the unit arcs at and imply that selected middle edges share neither left nor right endpoints. Thus they form a matching of the same value. By the integer max-flow theorem, a maximum flow can be chosen integer, so its value equals the maximum matching size.
The word integer matters: an arbitrary fractional feasible flow does not itself specify a matching.
Worked example 2.2.3
(A backward arc revises an assignment)
Suppose can use projects or , while can use only . If was first assigned to , the flow has one unit on , and the residual network contains the backward arc . The residual path uses it. Augmenting one unit cancels – and adds – and –.
The final flow has value and contains only allowed forward assignments: . Both students are now assigned, so no larger matching exists. The locally maximal one-edge assignment was not maximum.
A different certificate: cover the edges
Definition 2.2.4
(Vertex cover)
A vertex cover of is a set of vertices such that every edge of has at least one endpoint in .
Lemma 2.2.5
(Matchings never exceed covers)
In any finite graph, if is a matching and is a vertex cover, then .
Proof
(Assign a covering vertex to each matching edge)
Each edge of has an endpoint in ; choose one. Two distinct edges of share no endpoint, so they receive distinct vertices. This is an injection from into .
The lemma is useful only when we can exhibit a matching and a cover of equal size.
Theorem 2.2.6
(Matching-cover equality in bipartite graphs)
In a finite bipartite graph, the maximum matching size equals the minimum vertex-cover size.
Proof
(Build a cover from alternating reachability)
Start with a maximum matching . From every unmatched left vertex, follow alternating paths: traverse unmatched edges from left to right and matched edges from right to left. Let and be the reached left and right vertices. No reached right vertex is unmatched; otherwise the alternating path would augment .
Set . Every edge is covered. Indeed, if and is not in , the rule reaches ; if , a reached matched left vertex must have been reached through its matched right partner, so is reached as well. (An unmatched left vertex has no matched incident edge.) Thus an edge with left endpoint outside has its right endpoint in .
Every matched edge contributes exactly one vertex to : if its left endpoint is reached then so is its right endpoint; otherwise its right endpoint cannot be reached without following that matched edge back to the left. Every vertex of is matched, since unmatched left vertices were starting points, and every vertex of is matched, since no augmenting path exists. Hence . The lemma now proves that both are optimal.
The construction uses bipartiteness and a maximum matching; it does not assert the same equality for arbitrary graphs.
Proof X-ray
Where the two hypotheses do their work
The hypothesis that is a maximum matching is used exactly once: to guarantee that every reached right vertex is matched. Run the construction on a non-maximum matching and an unmatched right vertex can be reached; is still a cover, but that vertex is not paid for by any edge of , so and nothing is certified.
Bipartiteness is used in the shape of the search. Each edge has one end on each side, so the search alternates sides, and the cover can be chosen as unreached vertices on the left together with reached vertices on the right.
Key move: neither nor is a small cover by itself; the cover mixes the two sides, switching side exactly where alternating reachability stops.
How it closes: the proof never shows directly that is a minimum cover. It shows , and the lemma, applied to every cover and every matching, then makes both optimal at once.
Common mistake
(Taking the reached vertices as the cover)
The cover is : unreached on the left, reached on the right. Taking all reached vertices fails. In the bottleneck example below, with matching , this would give , which misses the edges and .
A worked bottleneck
Worked example 2.2.7
(Two students compete for one project)
Let , and . The matching has size two. The vertex cover meets all four edges and also has size two, so it certifies that no matching of size three exists. The obstruction is visible directly: both and have only project , and cannot both be matched.
A different matching is equally optimal. A certificate proves the objective value; it need not identify a unique optimal assignment.
Worked example 2.2.8
(A perfect matching leaves the search with no starting point)
Let , and , with matching . Every left vertex is matched, so the alternating search has no starting vertex: . The construction gives .
Check: covers and , and covers . Hence is a cover of size , and both are optimal. In this degenerate case the cover is the whole left side, as it must be whenever matches all of .
Counterexample mode
Matching-cover equality fails without bipartiteness
One might expect the maximum matching and the minimum cover to agree in every graph. Take a triangle on vertices . Any two of its three edges share a vertex, so the largest matching has size one. A single vertex meets only the two edges at it and misses the opposite edge, so every cover has at least two vertices; is a cover of size two. The sizes are . The lemma survives in every graph; equality requires the bipartite hypothesis.
Exercises
Quick check
(For edges , exhibit an alternating path that improves the matching and state the resulting matching.)
Start at the unmatched left vertex .
Solution · Answer
The residual alternating path replaces by , giving two matched edges.
Quick check
(For the bottleneck example, verify that is a cover and explain why it bounds every matching.)
Check each of the four edges.
Solution · Answer
Edges meet vertex and edges meet . Distinct matching edges cannot share either cover vertex, so at most two can be chosen.
Quick check
(In the bottleneck example, use matching and start alternating reachability at . Find and the constructed cover.)
Alternate unmatched edges left to right and matched edges right to left.
Solution · Answer
From reach , then the matched edge reaches ; no further vertex is reached. Thus , and .
Quick check
(Why does a fractional feasible flow of value not directly describe a matching of size ? What separate result permits an integer optimum?)
Compare what a matching is with what a flow assigns.
Solution · Answer
A matching is a set and has integer cardinality; fractional edge values need not be a set of selected edges. Integer capacities together with the integer max-flow theorem guarantee that some maximum flow is integer.