Motivation
Suppose jobs must be assigned to distinct workers, and each job has a list of acceptable workers. Choosing an available worker greedily may block a later job even when a complete assignment exists. An augmenting path repairs earlier choices: it alternates unused and used edges so that reversing their status increases the number of assignments by one.
For bipartite graphs, the same search also produces a certificate when no further improvement is possible. A vertex cover proves that a matching is maximum, and a deficient set of jobs explains why a complete assignment cannot exist. These witnesses turn an algorithmic answer into something independently checkable.
Definitions
Definition 3.10.1
(Bipartite graph, matching and matched vertex)
Let be a finite simple bipartite graph, with disjoint left and right vertex sets and every edge joining one vertex of each side. A matching contains no two edges with a common endpoint. A vertex incident to an edge of is matched; otherwise it is unmatched. The size of the matching is its number of edges.
Definition 3.10.2
(Augmenting path)
An augmenting path for is a simple path beginning at an unmatched vertex of , ending at an unmatched vertex of , and alternating between edges outside and edges in . Its first and last edges are outside . Flipping the status of every path edge removes the matched edges on the path and adds the other edges.
Definition 3.10.3
(Vertex cover and neighborhood)
A vertex cover is a set of vertices meeting every edge. For , its neighborhood is the set of vertices adjacent to at least one member of . The empty graph and empty matching are allowed; if is empty, a matching that covers all of exists trivially.
Theorems
Theorem 3.10.4
(Augmenting-path criterion)
A matching is maximum if and only if it has no augmenting path. Flipping an augmenting path produces a matching one edge larger.
Theorem 3.10.5
(Hall and matching-cover certificates)
A matching covering every vertex of exists if and only if for every . Moreover, every finite bipartite graph has a vertex cover whose size equals the size of a maximum matching.
Proofs
Why flipping works
Proof
(Flipping an augmenting path enlarges the matching)
An augmenting path starts and ends with unmatched edges and alternates, so it contains one more edge outside than inside . At an internal vertex, exactly one path edge was matched and exactly one was not; flipping exchanges them. At each endpoint, the newly added edge is the only matched edge because the endpoint was previously unmatched. Vertices outside the path retain their old status. Hence the flipped set is a matching of size .
Proof
(No augmenting path implies a maximum matching)
A maximum matching cannot have an augmenting path, since flipping would make it larger. For the converse, compare with any larger matching . Form their symmetric difference: retain edges belonging to exactly one matching. Each vertex has degree at most two there, with incident edges alternating between and . Every connected component is an alternating path, an alternating cycle, or an isolated vertex. Cycles have equally many edges of each matching. A path has at most one more edge of one matching than the other.
Because , some component path has one more edge than edge. Both its endpoint edges belong to , so its endpoints are unmatched by . In a bipartite graph this odd-length path has one endpoint on each side; orient it from to . It is an augmenting path for . Thus, if no augmenting path exists, no larger matching exists.
Proof X-ray
Compare two matchings by their symmetric difference
The proof has one idea: compare two matchings through the edges on which they disagree. Each vertex has at most one edge of and at most one edge of , so its degree in the symmetric difference is at most two. That is why the components are only paths and cycles. Along a path or cycle the edges alternate between and , so a cycle carries equally many edges of each and cannot account for . The surplus must therefore sit on paths, and a path carries a surplus of at most one. A path with one extra edge begins and ends with edges. No edge of can meet its endpoints: it would be a second edge unless it lay in both matchings, and a common edge is absent from the symmetric difference. So both endpoints are free for . Bipartiteness is used only at the end, to see that an odd path has one endpoint on each side. Without the hypothesis the difference could consist of cycles and balanced paths only, and no improvement would be forced.
Search and optimality certificate
Starting with any matching, direct every unmatched edge from to and every matched edge from to . Search this directed graph from all unmatched left vertices. If an unmatched right vertex is reached, predecessor pointers give an augmenting path. Flip it and repeat. Each flip increases the matching size, so at most flips occur. A search takes time with adjacency lists, giving time including the final search.
Proof
(A failed search yields a cover of the same size)
Suppose a final search finds no unmatched right vertex. Let and be the reached vertices on the two sides. Define
This is a vertex cover. Consider an edge . If , its left endpoint belongs to . If and the edge is unmatched, the directed search reaches . If the edge is matched, then a reached matched left vertex must have been reached along its unique matched edge from its mate ; an unmatched root has no matched incident edge. Thus in either case, and the edge is covered.
Every vertex of is matched, because reaching an unmatched right vertex would give an augmenting path. Its mate lies in . Conversely, the mate of every matched vertex of lies in , by the same search argument. A matched edge has either both endpoints reached or neither reached. Therefore the cover contains exactly one endpoint of every edge of , and no unmatched vertex: its size is exactly .
Any vertex cover has size at least that of any matching, because distinct matching edges require distinct cover vertices. Consequently and certify each other's optimality. This proves the matching-cover part of the theorem without assuming it beforehand.
Counterexample mode
Greedy assignment can get stuck
Let , , with edges . Greedily choosing leaves unmatched. The alternating path flips the old edge and adds , obtaining a matching of size two.
Reading the certificate
The final search has two possible uses. If it reaches an unmatched right vertex, predecessor links supply a concrete sequence of edge changes. If it does not, the reached sets supply a cover and, when a left root remains unmatched, a deficient neighborhood. These are different outcomes of the same exploration. A verifier need not trust the search implementation: it can check the matching, cover and neighborhood claims directly from the graph.
Concept lensAlgorithmic
Matching as an integral unit flow
The maximum matching also follows from a unit-capacity flow construction: connect a source to each left vertex, direct each original edge from left to right, and connect each right vertex to a sink. An integral unit of flow selects an edge, and unit capacities at the ends prevent two selected edges from sharing a vertex. The alternating paths above are the residual augmenting paths in this particular network. The direct proof here supplies the additional Hall witness and makes the reversal of earlier assignments visible.
Definition 3.10.6
(Maximal matching)
A maximal matching has no edge that can simply be added while retaining the matching property. Every maximum matching is maximal, but the converse fails in the greedy example: is maximal because both remaining edges touch an already matched endpoint, yet flipping an alternating path produces two edges. One-edge local checks therefore cannot replace the augmenting-path criterion.
Counterexample mode
Bipartiteness cannot be dropped from the cover equality
In a general graph a maximum matching and a minimum vertex cover can differ in size. Take the triangle with vertices and edges . Any two of its edges share a vertex, so a matching has at most one edge. A single vertex meets only two of the three edges: misses , and likewise for and . Every cover therefore needs at least two vertices, and is one. The maximum matching has size one while the minimum cover has size two. The triangle has an odd cycle, so it is not bipartite, and the equality of the theorem fails there.
Proof of Hall's condition
Proof
(Hall condition from a failed search)
If a matching covers , then distinct vertices in any are matched to distinct vertices of . Thus is necessary.
For sufficiency, take a maximum matching and assume it leaves some left vertex unmatched. Run the final alternating search. The set contains at least one unmatched root. Every neighbor of a reached left vertex is reached on the right: unmatched edges are traversed forward, and the matched edge of a reached matched left vertex leads to the already reached right vertex that discovered it. Conversely, every reached right vertex is reached from a left neighbor in . Hence .
All vertices of are matched to distinct vertices in . The reached left side also contains at least one unmatched root, so . This is an explicit violation of Hall's condition. The contrapositive proves sufficiency and yields a checkable deficient set whenever no left-covering matching exists.
Proof X-ray
Maximum size is used only to make the search fail
Sufficiency uses the maximum size of the matching once: a maximum matching guarantees that the final search fails. Failure means no unmatched right vertex is reached, so every vertex of has a mate, and that mate is reached too. Hence the matched vertices of and the vertices of correspond one to one, and the unmatched root adds one more left vertex, giving . The search is closed under traversal, so , and the count becomes for the explicit set . The violating set is read off from the failed search, not found by enumeration.
The condition applies to every subset of , not merely to single vertices. Each job having at least one acceptable worker does not guarantee that all jobs can be assigned simultaneously. A group of jobs may collectively have too few possible workers.
Worked examples
Worked example 3.10.7
(Repair a greedy matching)
For , and edges , start with . Search from unmatched : traverse forward, the matched edge backward, and forward. Vertex is unmatched. Flipping gives , which covers both left vertices.
Worked example 3.10.8
(A Hall obstruction)
Let and , with and adjacent only to , and adjacent to and . Each left vertex has a neighbor, but has . Since , no matching covers . The matching has maximum size two.
Worked example 3.10.9
(A cover certifies maximum size)
For the previous graph, covers all edges and has size two. The matching also has size two. No matching can have more edges than a vertex cover has vertices, so both are optimal without enumerating all possible matchings.
Worked example 3.10.10
(A side can be empty)
If and is any finite set, the empty matching covers every vertex of . Hall's condition has only the subset , for which . The empty vertex cover is also optimal because there are no edges.
Common mistakes
Common mistake
(Alternating is not the same as augmenting)
An alternating path is not automatically augmenting: both endpoints must be unmatched, which is what makes it contain one more unused edge than used edge. In the greedy example with , the path alternates, but its endpoint is matched. Flipping it replaces by and the size stays one. Flipping an alternating cycle likewise changes the selected edges without enlarging the matching.
Common mistake
(Equal sizes do not certify optimality by themselves)
A matching-cover certificate works only if the proposed set really meets every edge. In the graph with edges , the set has the same size as the matching , yet it misses , so it is not a cover. Verify that the edge set is a matching, check the cover property, and only then compare sizes.
Common mistake
(Hall's condition is about subsets, not single vertices)
Checking that every left vertex has a neighbor misses collisions between different left vertices. In the same graph , and each have a neighbor, yet has . When a maximum matching fails to cover the left side, the alternating search produces one concrete violating subset, so it is not necessary to enumerate all subsets to obtain the certificate.
Summary
Augmenting paths provide local improvements, and symmetric differences prove that the absence of such a path is globally decisive. A final alternating search yields a vertex cover of the same size as the matching. If some left vertex remains unmatched, the reached left set has too few neighbors, giving a Hall obstruction. These certificates explain both success and failure of an assignment.
Exercises
Quick check
(In the greedy example, write the edge statuses before and after flipping the path .)
List the three edges , , one by one.
Solution · Answer
Initially is matched, while and are unmatched. Flipping removes and adds and , so afterwards is unmatched and are matched. The result is a matching of size two rather than one.
Quick check
(Let three left vertices all be adjacent only to two right vertices. Give a Hall obstruction and an upper bound on matching size.)
Try equal to the whole left side.
Solution · Answer
Take to be all three left vertices. Its neighborhood has at most two vertices, so . Every matching uses a different right endpoint for each of its edges, so its size is at most two.
Exercise 3.10.11
(A matching and a vertex cover of the same graph satisfy . Prove that is a maximum matching and is a minimum vertex cover.)
CoreProof
Both sets live in one graph, and only the sizes are known.
Hint(1)
Distinct edges of a matching share no endpoint, so a cover needs a separate vertex for each of them.
Solution(3)
- 1
Compare any matching with any cover
Key step
For every matching and every vertex cover of the graph,
Because: Distinct matching edges have no common endpoint, and each edge needs a cover vertex.
- 2
Bound every cover from below
Taking gives for every cover . Since , the cover has the least possible size.
- 3
Bound every matching from above
∎Taking gives for every matching . Since , the matching is maximum, and is a minimum vertex cover.
Quick check
(If a matching covers all vertices of , explain why every subset has at least neighbors, including .)
Send each vertex of to its partner.
Solution · Answer
The matching sends each vertex of to a distinct right neighbor, which gives an injection from to . Thus . For the empty set this is the true inequality .