Matching is a global allocation problem
Definition 3.3.1
(Bipartite graph, matching and neighborhood)
Let be a finite bipartite graph, with every edge joining a left vertex to a right vertex. A matching contains no two edges sharing an endpoint. A vertex not incident to a matching edge is unmatched. A matching saturates if every left vertex is matched. For , write for all right vertices adjacent to at least one vertex of .
A local choice can prevent another vertex from being matched, even when a better allocation exists. Alternating paths repair such choices, and a failed search can itself certify that no larger matching is possible. This lesson builds on residual paths for network flow but proves the matching-specific certificate directly.
Alternating search and augmentation
Definition 3.3.2
(Augmenting path)
An augmenting path starts at an unmatched left vertex and ends at an unmatched right vertex, alternating edges outside and edges in . Its first and last edges are outside . Flipping the path means replacing by its symmetric difference with the path: remove each old matching edge on the path and add each previously unused path edge.
Theorem 3.3.3
(Augmenting step)
Flipping an augmenting path of yields a matching of size .
Proof
(Flipping an augmenting path adds one edge)
Every internal vertex of the path loses one matching edge and gains one, so it is still incident to exactly one matching edge. Both endpoints were unmatched, and each gains one matching edge. Vertices off the path are unaffected. Hence the result is a matching. The path has one more edge outside than inside , so the new size is .
To find such a path, start a graph search simultaneously at all unmatched left vertices. From a reached left vertex traverse edges outside to the right; from a reached right vertex traverse its matching edge, if present, to the left. Record a predecessor only on first reaching a vertex. These pointers form a search forest: following them back from an unmatched reached right vertex gives a simple path to an unmatched left root, with the required alternation. Otherwise the search ends with reached sets and . A visited set prevents cycles; after augmentation, run a fresh search because the matching has changed.
A maximum matching and a minimum cover
Definition 3.3.4
(Vertex cover)
A vertex cover is a set of vertices meeting every edge.
Theorem 3.3.5
(Kőnig's theorem)
Every vertex cover has size at least for every matching . In a finite bipartite graph, the maximum size of a matching equals the minimum size of a vertex cover, and the alternating search produces both.
Proof
(A failed search gives a cover of the same size)
Every cover has size at least for every matching , because each matching edge needs a cover vertex and distinct matching edges share no endpoint.
Suppose the alternating search finds no augmenting path. Then every vertex in is matched, for an unmatched reached right vertex would finish such a path. Furthermore . Indeed, every nonmatching edge from a reached left vertex is traversed; if its matching edge exists, that matched right vertex was already reached just before the left vertex. Conversely every reached right vertex was reached from a left neighbor.
Now define
Every edge is covered: an edge from outside meets its left endpoint in , while an edge from has its right endpoint in . Every matching edge has exactly one endpoint in : its endpoints are either both reached or both unreached. Every vertex in is matched, since unmatched left vertices start the search and unmatched right vertices cannot be reached. Therefore . The matching and cover give equal lower and upper certificates, so is maximum and is minimum. This proves Kőnig's theorem.
Proof X-ray
Why the failed search is a complete certificate
The proof reads two facts off the stopping condition. No unmatched right vertex was reached, so every vertex of has a mate, and that mate lies in . The search follows every non-matching edge out of and every matching edge out of , so it is closed, which gives and shows that no matching edge has exactly one reached endpoint. Together these make a cover with exactly one endpoint on each matching edge and no unmatched vertex, so , and the weak bound finishes the argument. Bipartiteness enters in the cover check: every edge has its left endpoint either outside or inside it, and in the second case the closure of the search puts its right endpoint in . A graph with an odd cycle has no such left–right split, which the counterexample below exploits.
Starting with the empty matching and repeatedly augmenting must terminate, as the size increases by one and is bounded by . The final failed search supplies the certificate above; hence the algorithm is correct without assuming a greedy choice is permanent. With adjacency lists, one search costs , so at most successful searches plus one final failed search give time. This is a simple bound, not a claim about the best possible algorithm.
Counterexample mode
Kőnig's equality needs bipartiteness
Consider the claim that in every graph the maximum size of a matching equals the minimum size of a vertex cover. Take a triangle with vertices and edges . Any two of its edges share a vertex, so every matching has at most one edge. No single vertex meets all three edges, because misses , and likewise for and . The set is a cover. So the maximum matching has size one while the minimum cover has size two. The triangle contains an odd cycle, so it is not bipartite and the left–right split used by the search does not exist. The repaired claim restricts the equality to bipartite graphs; for general graphs only the inequality survives.
Hall's condition follows from the search
Theorem 3.3.6
(Hall's theorem)
A finite bipartite graph has a matching saturating if and only if for every .
Proof
(Hall's condition from the failed search)
Necessity is immediate: the matching sends distinct vertices of to distinct neighbors. For sufficiency, run the augmentation algorithm to a maximum matching. If some left vertex remains unmatched, the failed search has at least one unmatched root in . Every reached right vertex is matched to a distinct reached left vertex, and every reached matched left vertex has its matching partner in . Thus . Since , the set violates Hall's condition. The contrapositive completes the proof. Checking all subsets directly is not required by the algorithm: the failed search produces a violating set when one exists.
Concept lensAlgebraic
Kőnig's theorem as a statement about a table of 0s and 1s
Record as a table with a row for each left vertex and a column for each right vertex, with a in position exactly when . A matching is a set of s, no two in the same row or column. A vertex cover is a set of rows and columns that together contain every . Kőnig's theorem says that the largest number of such independent s equals the fewest rows and columns containing all s. In the worked trace below, the three columns contain every , and three independent s exist.
Worked trace and two certificates
Worked example 3.3.7
(Two searches on a four-vertex example)
Take and , with edges –, –, –, –, – and –. Begin with . Both and are unmatched; a search can choose the augmenting path , yielding .
Start again at the only unmatched left vertex . Alternating reachability follows
where left-to-right arrows use nonmatching edges and right-to-left arrows use matching edges. Every right vertex is reached and matched, so no augmenting path remains. Here , , and is a cover of size three, equal to the matching size. Also has only three neighbors for four vertices, exhibiting the Hall obstruction to saturating . The trace demonstrates a particular search order; the certificate does not rely on the order of scanning edges.
Worked example 3.3.8
(An isolated left vertex)
Take and with the single edge –, so has no neighbors. From the empty matching, search from both unmatched left vertices. The vertex reaches the unmatched right vertex , so – is an augmenting path and . A second search starts at alone and reaches nothing else: and . Then covers the only edge and has size one, equal to . The violating set is with , so . A deficient set can be a single vertex without any neighbor.
Worked example 3.3.9
(Rerouting an earlier choice)
Take , with edges –, –, –, and the matching produced by a local choice. The only unmatched left vertex is . The search goes along a non-matching edge, along the matching edge, and along a non-matching edge. The right vertex is unmatched, so is an augmenting path. Flipping it removes – and adds – and –, giving a matching of size two that saturates . The earlier choice of – was undone rather than kept.
Common mistakes
Common mistake
(Hall's condition is about subsets, not single vertices)
Checking that every left vertex has a neighbor is not enough, because different left vertices may compete for the same right vertices. In the graph with edges –, –, –, every left vertex has a neighbor, yet has and no matching saturates . The failed search produces such a subset, so the subsets need not be enumerated.
Common mistake
(Equal sizes do not make a certificate)
A matching and a vertex set of equal size certify optimality only if the set really is a cover. Take edges –, –, –, –. The matching and the set both have size two, but misses the edge –, so it is not a cover and certifies nothing. Check the cover property edge by edge before comparing sizes.
Exercises
Quick check
(For , and edges –, –, –, give a maximum matching, a cover of equal size and a Hall-violating subset.)
Look for two left vertices that share a single neighbor.
Solution · Answer
The matching has size two. The set meets every edge and has size two, so both are optimal. The subset has , so , and no matching saturates .
Quick check
(Explain why flipping an augmenting path changes the matching size by exactly one, including what happens at its endpoints.)
Count the path edges inside and outside .
Solution · Answer
The path has one more edge outside than inside , so flipping adds one edge more than it removes. Each internal vertex swaps one matching edge for another and stays matched once. Each endpoint was unmatched, receives one new matching edge, and becomes matched once.
Quick check
(Why can the matching and the proposed cover fail to certify equal optimum sizes if the alternating search is stopped before it exhausts all reachable vertices?)
Is the reached set closed under the traversal rules?
Solution · Answer
The sets and are then not closed under the traversal rules. A reached left vertex may have a non-matching edge to a right vertex not yet in . That edge has no endpoint in , so need not be a cover. An unreached right vertex might also be unmatched, in which case an augmenting path still exists and is not maximum. Only an exhausted search gives both properties.