Motivation
A collection of individually acceptable assignments may still be impossible to realize simultaneously. Several requests can compete for too few available choices. A matching records assignments with no shared endpoint. The central question is whether a failed attempt reveals a genuine shortage or merely a poor earlier decision.
Alternating paths distinguish those situations. They can undo some chosen assignments while making one more assignment overall. If no such improvement exists, the failed search itself identifies a set with too few neighbors and constructs a minimum vertex cover. A single argument will therefore explain an algorithm, an existence theorem and an equality between two optimization problems.
Definitions
Definition 6.1.1
(Matchings and vertex covers)
A matching in a finite simple graph is a set of edges with pairwise disjoint endpoints. A vertex is saturated by when one edge of meets it. A maximum matching has largest possible size; a maximal matching cannot be enlarged by adding a single edge. A perfect matching saturates every vertex. A vertex cover is a set of vertices meeting every edge.
A bipartite graph has a specified disjoint vertex partition , with every edge joining the two parts. For , its neighbor set is . A matching saturating need not saturate when the parts have different sizes.
Definition 6.1.2
(Alternating and augmenting paths)
Relative to a matching , an alternating path has edges alternately outside and inside . An augmenting path has distinct vertices, begins and ends at unsaturated vertices, and its first and last edges are outside . Thus it has an odd number of edges and one more edge outside than inside it.
Replacing the matching edges on an augmenting path by its other edges is called augmentation. Internal vertices remain saturated, the two endpoints become saturated, and vertices off the path are unchanged. These local facts show that augmentation produces another matching, larger by exactly one.
Theorem/Proposition
Theorem 6.1.3
(Augmenting-path criterion)
A matching in a finite graph is maximum if and only if there is no augmenting path relative to it. This criterion does not require bipartiteness.
Theorem 6.1.4
(Hall's condition)
A finite bipartite graph with parts has a matching saturating if and only if for every subset . The empty subset is included and satisfies the inequality automatically.
Theorem 6.1.5
(König's matching–cover equality)
In a finite bipartite graph, the maximum size of a matching equals the minimum size of a vertex cover. More precisely, a maximum matching determines a cover of the same size by the alternating-reachability construction proved below.
Proof sketch or proof idea
Proof
(Comparing two matchings through their symmetric difference)
An augmenting path increases the matching size, so a maximum matching cannot have one. Conversely, suppose a matching is smaller than another matching . Consider the graph with edge set , the edges belonging to exactly one of them. Every vertex has degree at most two, and every nontrivial component is a path or a cycle with alternating edge types. Cycles contain equally many of each type. Since , some path contains one more -edge than -edge. It begins and ends with -edges.
Its endpoints are unsaturated by . An endpoint cannot have another -edge in the symmetric difference, because it is an endpoint there. It cannot have a common - and -edge either, because its incident -edge already belongs to the path and is a matching. Thus this path is -augmenting, proving the criterion.
Proof
(Alternating reachability gives Hall's witness and a cover)
For the bipartite results, choose a maximum matching and let be the unsaturated vertices in . Direct every unmatched edge from to and every matched edge from to . Let be the vertices reachable from in the two parts, allowing length-zero reachability at the roots.
No vertex of is unsaturated: a directed path to such a vertex would be augmenting. Every reached vertex in is therefore matched, and its matched partner lies in . Conversely, every vertex of was reached through its matched edge, so its partner lies in . The matching pairs these two sets bijectively, giving
Moreover . Every reached right vertex was reached from a left neighbor. Every unmatched edge from a reached left vertex can be followed; its matched edge, if present, leads to the right vertex through which that left vertex was reached. Hence all its neighbors are reached.
Necessity of Hall's condition is direct: a matching saturating sends distinct vertices of any to distinct neighbors. For sufficiency, if were nonempty, the constructed set would satisfy
contradicting Hall's condition. Thus saturates .
Finally set . An edge with left endpoint outside is covered there; an edge whose left endpoint is in has its right endpoint in . Therefore covers every edge. Its size is
Any cover has at least one distinct vertex for every matching edge, so no cover can be smaller than a matching. The constructed equality proves König's theorem.
Proof X-ray
Where maximality and bipartiteness enter
The bipartite proof uses maximality of exactly once: no reached right vertex is unsaturated, since otherwise the search would have found an augmenting path. Everything else follows from the orientation. Unmatched edges point from to and matched edges back, so a reached right vertex is left only along its matched edge; this gives the partner bijection between and , hence . Closure of reachability gives , and that single equality does double duty. With it makes a Hall-deficient set. Read as “no edge leaves for ”, it makes a cover. Bipartiteness is what lets one orientation encode the alternation; in a general graph a vertex can be reached at both parities, and the partner bijection breaks.
Worked examples
Worked example 6.1.6
(A maximal matching that can be repaired)
Let , and take edges . The matching is maximal: no remaining edge can be added without sharing an endpoint. Yet is an augmenting path. Replace by to obtain a matching of size two. The repair temporarily reverses an earlier assignment; a rule allowing only additions would miss it.
Worked example 6.1.7
(A deficiency set and a smallest cover)
Let , with edges . The set has only neighbor , so no matching saturates . Take . From root , alternating reachability gives and . The cover is , of size two. This both certifies that is maximum and that the cover is minimum. The whole left set has three neighbors, so checking only the whole set would have missed the obstruction.
Worked example 6.1.8
(Every positive regular bipartite graph has a perfect matching)
Suppose a finite nonempty bipartite graph is -regular, where . Counting edges from the two parts gives , hence equal part sizes. For any , exactly edges leave , and all end in , whose vertices have at most incident edges altogether. Thus . Hall gives a matching saturating ; equal part sizes make it perfect. The positivity condition permits cancellation of and excludes isolated-vertex counterexamples.
Why the symmetric difference is the right comparison
Comparing matching sizes alone says that an improvement exists, but not how to find or understand it. The symmetric difference removes the edges on which two proposed matchings already agree. What remains has a rigid local structure because neither matching uses two edges at one vertex. Degree at most two forces paths and cycles, and alternating edge types force a simple accounting of their size differences.
A path with the same number of the two edge types merely trades assignments. A cycle does the same. Only a path with one extra edge of the larger matching can increase cardinality. This is why an improvement may need several reversals but never needs an arbitrary branching rearrangement. The augmenting path isolates one useful component of the comparison.
The criterion proves optimality in all finite graphs, but searching efficiently for augmenting paths is easier in bipartite graphs. There the fixed partition and edge orientation organize a direct reachability search. In a nonbipartite graph, odd alternating structures can make a naive search inadequate. The theorem remains true; the simple bipartite search procedure is the part that needs the additional hypothesis.
Turning the proof into an algorithm
Start with the empty matching. In the directed alternating graph, search from all unsaturated left vertices. If an unsaturated right vertex is reached, use parent links to extract a simple directed path and augment. Rebuild the orientation for the new matching and repeat. Each augmentation increases the number of edges by one, so at most the smaller part size many augmentations are possible.
If no unsaturated right vertex is reached, the same reachable-set proof constructs a cover with the current matching's size. Thus the stopping condition certifies maximum cardinality; it is not merely a failure of a particular greedy choice. In particular, an earlier bad assignment can be corrected during a later search, as in the first example.
Using adjacency lists, each search takes time, including initializing reachability data. Repeating it gives a straightforward bound of . This is a bound for this elementary algorithm, not the best known bound for bipartite matching. Keeping the vertex term matters when many isolated vertices are present. A denser representation can change the search cost even though the proof is unchanged.
Measuring how many requests must remain unassigned
Define the maximum deficiency to be the largest value of over subsets of . It is nonnegative because the empty set gives zero. For any matching and any such subset, at most the number of its neighbors can be matched, so at least its deficiency many left vertices must remain unmatched.
For a maximum matching, the alternating reachable set attains this lower bound. The equality between reached left vertices, reached right vertices and unmatched roots says that its deficiency is exactly the number of unmatched left vertices. Consequently
Hall's theorem is precisely the zero-deficiency case. The formula also explains why the failure certificate can be more informative than a yes-or-no answer: it quantifies an unavoidable shortage. No assumption that the two parts have equal size is needed.
Concept lensStructural
A feasible construction and a universal bound meet
A matching exhibits assignments that can coexist. A cover supplies an upper bound on every matching because each disjoint edge needs its own covering vertex. Finding both with the same size proves optimality on both sides. The deficient subset gives a different upper bound by identifying requests competing for too few neighbors. These are checkable certificates rather than appeals to the search history.
Covers, independent sets and the role of bipartiteness
The complement of a vertex cover is an independent set: an edge with both endpoints outside the cover would be uncovered. Conversely, the complement of an independent set covers every edge. Thus maximum independent-set size plus minimum cover size equals the number of vertices in any finite graph. Combined with König's theorem, this computes an independent-set optimum in a bipartite graph from a matching and its cover.
This deduction does not make independent sets easy in all graphs. The cover–independent-set complement identity is universal, while equality between cover size and matching size is specifically bipartite. Keeping those two scopes separate prevents a valid identity from being used to transfer an optimization method beyond its hypotheses.
Common mistakes
Counterexample mode
Matching–cover equality fails on a triangle
A triangle has maximum matching size one because any two edges share a vertex. Its smallest vertex cover has size two: one vertex misses the opposite edge, while any two cover all three edges. Hence the two optimum sizes differ. Bipartiteness is essential to König's equality, even though every matching is still bounded by every vertex cover.
Common mistake
(Global balance does not imply Hall's condition)
Hall's condition tests every subset of the side to be saturated. Equal part sizes, enough total edges or the absence of isolated vertices is insufficient. The deficient pair in the second example has no isolated vertex and is invisible to the whole-side neighbor count.
Common mistake
(Vertex covers are not edge covers)
A vertex cover is a set of vertices meeting every edge; an edge cover is a set of edges meeting every vertex. These are different optimization problems. On the path with edges , the set is a minimum vertex cover of size one, while every edge cover needs both edges, because lies only on and only on .
Summary
Augmentation repairs a matching by exchanging alternating edges. Symmetric differences prove that the absence of an augmenting path characterizes maximum cardinality. In bipartite graphs, alternating reachability simultaneously gives Hall's shortage witness and a cover of matching size, establishing both Hall's theorem and König's theorem constructively.
Exercises
Quick check
(For left vertices and right vertices , take edges . Find a maximum matching and a minimum vertex cover.)
Provide equal-size feasible objects as an optimality certificate.
Solution · Answer
The edges form a matching of size three. The whole right side is a cover of size three, so both are optimal by the matching–cover bound. In particular no matching can saturate all four left vertices. The subset has only neighbors and certifies a deficiency of one.
Quick check
(If a bipartite graph has a matching saturating , prove that deleting one left vertex and its matched right vertex leaves a graph with a matching saturating the remaining left side.)
Do not confuse this with deleting an arbitrary right vertex.
Solution · Answer
Remove the unique matching edge incident to the chosen left vertex. Its right endpoint is the deleted right vertex, and no other matching edge uses either endpoint. Every other left vertex therefore retains its original matching edge in the remaining graph. This constructs the required saturating matching. Deleting an unrelated right vertex could destroy another necessary edge and need not preserve saturation.
Quick check
(Give a bipartite graph with equal part sizes, no isolated vertices, and no perfect matching.)
Explain the failure using a specific Hall subset.
Solution · Answer
Use , and edges . Every vertex has positive degree and both parts have size three. Nevertheless , violating Hall's inequality. Any matching has at most one edge for and at most one for , so has size at most two; attains that bound.