Reading an Augmentation as a Sequence of Changes
Augmenting a matching is a local operation: find a path whose edges alternate between outside and inside the current matching, then exchange the path's matched and unmatched edges. The important work when tracing by hand is to keep track of the current matching at every step. An edge that is available for a search at one stage may be matched at the next, and every update must leave each vertex incident to at most one selected edge.
All graphs in this tutorial are finite and simple. A bipartite graph \(G=(V,E)\) has a specified partition \(V=L\cup R\), where \(L\cap R=\varnothing\), and every edge joins a vertex in \(L\) to one in \(R\). A matching \(M\subseteq E\) is a set of edges no two of which share a vertex. A vertex is matched if it is incident to an edge of \(M\); otherwise it is unmatched. The size of the matching is \(|M|\).
On a bipartite graph, an augmenting path can be traced starting at an unmatched vertex of \(L\): follow an edge outside \(M\) from \(L\) to \(R\), then, if the reached vertex of \(R\) is matched, follow its matching edge back to \(L\). Continue alternating until an unmatched vertex of \(R\) is reached. A search can make different choices when several edges are available; the path found and the intermediate matchings can therefore depend on those choices.
Why Flipping Works
Proof. Write the edges of \(P\), in order, as \(e_1,e_2,\ldots,e_{2k+1}\), where \(e_1,e_3,\ldots,e_{2k+1}\) are outside \(M\) and \(e_2,e_4,\ldots,e_{2k}\) are in \(M\). The path has odd length because its first and last edges are outside \(M\) and the edge types alternate. Define \(M'=(M\setminus\{e_2,e_4,\ldots,e_{2k}\})\cup\{e_1,e_3,\ldots,e_{2k+1}\}\). Each internal vertex of \(P\) is incident to one removed matching edge and one added edge, so it is still incident to exactly one edge of \(M'\). Each endpoint was unmatched and gains exactly one incident edge. Vertices outside \(P\) keep their matching status. Thus no two edges of \(M'\) share a vertex, so \(M'\) is a matching. The path contributes \(k+1\) added edges and \(k\) removed edges, giving \(|M'|=|M|+1\). \(\square\)
This count gives a useful record-keeping check: every successful augmentation raises the matching size by exactly one, regardless of the length of the path. The longer path changes which vertices are matched, but not the size increase.
Worked Augmentations
Worked Example: Three Successive Augmentations
Let \(L=\{a,b,c,d\}\), \(R=\{1,2,3,4\}\), and let the edge set be \(E=\{a1,a2,b1,b3,c2,c3,d3,d4\}\). Start with the empty matching and use the indicated augmenting paths.
| Stage | Search path and edge status before flipping | Matching after the step | Size |
|---|---|---|---|
| Start | No path used | \(M_0=\varnothing\) | 0 |
| 1 | \(a-1\): \(a1\) is unmatched | \(M_1=\{a1\}\) | 1 |
| 2 | \(b-1-a-2\): \(b1\notin M_1,\ a1\in M_1,\ a2\notin M_1\) | \(M_2=\{b1,a2\}\) | 2 |
| 3 | \(c-2-a-1-b-3\): \(c2\notin M_2,\ a2\in M_2,\ a1\notin M_2,\ b1\in M_2,\ b3\notin M_2\) | \(M_3=\{c2,a1,b3\}\) | 3 |
| 4 | \(d-4\): \(d4\notin M_3\) | \(M_4=\{c2,a1,b3,d4\}\) | 4 |
For stage 2, remove \(a1\) and add \(b1,a2\), so \(M_2=\{b1,a2\}\). For stage 3, remove \(a2,b1\) and add \(c2,a1,b3\), so \(M_3=\{c2,a1,b3\}\). At stage 4, \(d4\) has two unmatched endpoints, so it is itself an augmenting path and is added. At each stage the listed edges share no endpoints within the resulting matching.
Check: The sizes computed from the edge sets are \(|M_1|=1\), \(|M_2|=2\), \(|M_3|=3\), and \(|M_4|=4\). In \(M_4\), the four edges \(a1,c2,b3,d4\) have distinct left endpoints \(a,c,b,d\) and distinct right endpoints \(1,2,3,4\); hence \(M_4\) is a matching saturating both parts. No matching can have more than four edges because \(|L|=|R|=4\), so this one is maximum.
Worked Example: Rerouting an Earlier Choice
Let \(L=\{p,q,r\}\), \(R=\{x,y,z\}\), and \(E=\{px,py,qx,rz\}\). Begin with \(M_0=\{px,rz\}\). This matching has size two, but \(q\) is unmatched. Search from \(q\): its edge \(qx\) is matched to \(p\) by \(px\), and \(p\) has an edge \(py\) outside the matching. The resulting path is \(q-x-p-y\).
| Path position | Edge | Status in \(M_0\) | Action |
|---|---|---|---|
| 1 | \(qx\) | Outside \(M_0\) | Add |
| 2 | \(xp\), the edge \(px\) | In \(M_0\) | Remove |
| 3 | \(py\) | Outside \(M_0\) | Add |
After flipping, \(M_1=(M_0\setminus\{px\})\cup\{qx,py\}=\{qx,py,rz\}\). The change in size is \(2-1=1\), so \(|M_1|=|M_0|+1=3\). This path reroutes \(p\): it was matched to \(x\) and becomes matched to \(y\), allowing \(q\) to use \(x\).
Check: The edges \(qx,py,rz\) have distinct endpoints, so \(M_1\) is a matching. Since \(|L|=|R|=3\), no matching can exceed three edges; thus \(M_1\) is maximum. The check also shows why an augmenting path need not simply add an edge: one old edge is removed while two new ones are added.
Worked Example: A Search with No Augmenting Path
Let \(L=\{u,v,w\}\), \(R=\{1,2,3\}\), and \(E=\{u1,u2,v1,v2,w2\}\). Consider \(M=\{u1,v2\}\). The only unmatched vertex in \(L\) is \(w\), and the unmatched vertices in \(R\) are \(3\) (and no other right vertex). Trace the alternating search from \(w\), following unmatched edges from left to right and matching edges from right to left.
| Search stage | Reached vertices | Next permitted move | Result |
|---|---|---|---|
| 0 | \(w\) | Follow unmatched edge \(w2\) | Reach \(2\) |
| 1 | \(w,2\) | Vertex \(2\) is matched by \(v2\); follow \(2v\) | Reach \(v\) |
| 2 | \(w,2,v\) | From \(v\), follow unmatched edge \(v1\) | Reach \(1\) |
| 3 | \(w,2,v,1\) | Vertex \(1\) is matched by \(u1\); follow \(1u\) | Reach \(u\) |
| 4 | \(w,2,v,1,u\) | From \(u\), \(u1\) is matched and \(u2\) leads to already reached \(2\) | No new vertex; search ends |
The reached right vertices are \(1\) and \(2\), both matched. The unmatched right vertex \(3\) is not reached, so this search has not found an augmenting path. There are no other unmatched left roots to search. Thus no augmenting path exists for \(M\).
Check: The two edges in \(M\) have distinct endpoints, so \(M\) is a matching of size \(2\). The only right vertices incident to any edge are \(1\) and \(2\); therefore every matching has at most two edges. This independently confirms that \(M\) is maximum. Vertex \(3\) is isolated, and its being unmatched does not prevent a maximum matching.
From the Trace to a Maximum Matching
A sequence of augmentations is useful only if we know when to stop. Berge's theorem states that a matching in a finite graph is maximum if and only if there is no augmenting path for it. This theorem was established in the earlier material on augmenting paths. For hand tracing, its practical meaning is precise: after each flip, update the matching and search again; when a complete search finds no augmenting path, the current matching is maximum.
In a bipartite search, keep the direction rules tied to the current matching. From a left vertex, explore only edges outside the matching; from a right vertex, if it is matched, follow its unique matching edge back to the left. Reaching an unmatched right vertex completes an augmenting path. If the search ends without reaching one, no augmenting path starts at any of the unmatched left vertices that were used as search roots.
List its edges and mark the unmatched vertices in each part. Do this again after every augmentation.
From unmatched left vertices, follow edges outside the matching to the right; from a matched right vertex, follow its matching edge back to the left.
The recorded route is an augmenting path. If the search is exhausted without reaching one, the matching is maximum by Berge's theorem.
Remove the path's matched edges, add its other edges, verify that the result is a matching, and increase the size count by one.
Each successful augmentation increases the matching size by one. Since a bipartite matching has at most \(\min(|L|,|R|)\) edges, only finitely many augmentations are possible. More generally, for any finite graph with vertex set \(V\), every matching has at most \(\lfloor |V|/2\rfloor\) edges, because each matching edge uses two distinct vertices. Thus the termination bound does not depend on bipartiteness; bipartiteness is used for the left-right search procedure described here.
Common Mistake: Adding Without Removing
In the rerouting example, a wrong update would be to add \(qx\) and \(py\) to \(M_0=\{px,rz\}\) without removing \(px\). The result \(\{px,qx,py,rz\}\) is not a matching: both \(px\) and \(qx\) use vertex \(x\). The correct operation is the symmetric exchange along the path: remove \(px\), then add \(qx\) and \(py\), giving \(\{qx,py,rz\}\). Always mark the path edges in their status before flipping; do not decide which edges to remove by looking only at the final list.
A second check is to count the path edge types. An augmenting path has one more unmatched edge than matched edge. If a proposed flip does not increase the matching size by exactly one, either the path was not augmenting or the update was recorded incorrectly.
Check Your Understanding
For each question, write down the current matching before making any change, then verify the resulting edge set.
- In the first worked example, why is \(c-2-a-1-b-3\) an augmenting path for \(M_2\)? List its edges in order and their statuses.
- In the second example, which vertex changes partner during the augmentation, and why does the matching size increase by one rather than two?
- In the third example, identify the unmatched left and right vertices. Why does the search not produce an augmenting path?
- Explain why flipping an alternating path preserves the matching condition at every internal vertex.
- For a finite graph on \(n\) vertices, why can no matching have more than \(\lfloor n/2\rfloor\) edges?