Small Definition Errors Can Change the Conclusion
Arguments about bipartite matchings often use a few related terms in quick succession: maximal, maximum, alternating, augmenting, vertex cover, and edge cover. Their definitions are close enough to invite slips, but each has a specific role. In this tutorial, graphs are finite and simple. A matching is a set of edges no two of which share an endpoint. A vertex is saturated by a matching if it is incident with an edge of that matching; otherwise it is unsaturated.
The distinction is about two different comparisons. Maximality asks whether one can add edges to the particular matching while keeping all its existing edges. Maximum size compares it with every matching, including ones formed by removing some of its edges and choosing different ones.
A path of length zero, consisting of one vertex, has no edges to alternate. Even if it is treated as alternating vacuously, it is not an augmenting path: positive length is required. In a path of positive length the endpoints are distinct, so the two unsaturated endpoints are genuinely different vertices. This detail matters when stating that augmenting paths have odd length and when claiming that flipping one increases the matching size.
Worked Example: Maximal Does Not Mean Maximum
Worked Example: A Matching That Cannot Be Enlarged by Adding an Edge
Let \(G=(V,E)\) be the bipartite graph with parts \(\{1,3\}\) and \(\{2,4\}\), where \(V=\{1,2,3,4\}\) and \(E=\{12,23,34\}\). Consider \(M=\{23\}\).
The only edges outside \(M\) are \(12\) and \(34\). Edge \(12\) shares vertex \(2\) with \(23\), and edge \(34\) shares vertex \(3\) with \(23\). Thus neither can be added to \(M\) while retaining \(23\). So \(M\) is maximal.
However, \(N=\{12,34\}\) is a matching: its two edges have no common endpoint. Its size is \(|N|=2\), whereas \(|M|=1\). Therefore \(M\) is not maximum. A common incorrect argument says, “No edge can be added, so this matching is maximum.” The check above proves only maximality; it does not compare \(M\) with matchings that replace \(23\).
Check: The graph has four vertices, and the two disjoint edges in \(N\) use all four, so no matching can have more than two edges. Thus \(N\) is maximum, confirming that the maximal matching \(M\) is smaller than a maximum one.
What an Augmenting Path Allows You to Do
Along an augmenting path, the first and last edges are outside \(M\), because the endpoints are unsaturated. Alternation then forces the path to have odd length. The edge-flipping operation removes the edges of \(M\) on the path and adds the other path edges. It does not add every path edge while keeping the old matching edges.
Proof. Let \(P\) have length \(\ell\). Its first and last edges are outside \(M\), and its edges alternate, so \(\ell\) is odd. Write \(\ell=2k+1\), where \(k\) is a nonnegative integer. Then \(P\) has \(k\) edges in \(M\) and \(k+1\) edges outside \(M\). Define \(M'\) by removing the \(k\) edges of \(P\) that belong to \(M\) and adding the other \(k+1\) edges of \(P\), while leaving all edges of \(M\) outside \(P\) unchanged. Each internal vertex of \(P\) is incident with one added path edge and one removed path edge; each endpoint was unsaturated and becomes incident with just one added path edge. Since \(P\) is a path and \(M\) was a matching, no vertex on \(P\) conflicts with an edge of \(M\) outside \(P\). Hence \(M'\) is a matching, and \(|M'|=|M|-k+(k+1)=|M|+1\). The positive-length condition ensures \(k+1\ge1\), so this is a genuine increase. \(\square\)
Worked Example: Flip the Path, Do Not Keep Its Old Edges
Let \(G=(V,E)\) have parts \(\{a,c\}\) and \(\{b,d\}\), with \(V=\{a,b,c,d\}\), \(E=\{ab,bc,cd\}\), and \(M=\{bc\}\). The path \(P=a,b,c,d\) has edges \(ab,bc,cd\), which are outside \(M\), in \(M\), outside \(M\), respectively. Its endpoints \(a,d\) are unsaturated, so \(P\) is an augmenting path of positive length \(3\).
Flipping removes \(bc\) and adds \(ab\) and \(cd\). Thus \(M'=(M\setminus\{bc\})\cup\{ab,cd\}=\{ab,cd\}\), and \(|M'|=0+2=2\), while \(|M|=1\). The two new edges are disjoint, so \(M'\) is indeed a matching.
A wrong calculation would keep \(bc\) and add \(ab,cd\), obtaining \(\{ab,bc,cd\}\). This is not a matching: \(ab\) and \(bc\) both meet at \(b\), and \(bc\) and \(cd\) both meet at \(c\). The correction is to remove every matched edge on the path before adding the unmatched path edges.
Check: The graph has only three edges, and every pair among them shares an endpoint except \(ab\) and \(cd\). Thus its largest matching has size \(2\), exactly the size of \(M'\).
Proof. If there is an augmenting path, the proposition gives a matching of size \(|M|+1\), so \(M\) is not maximum. For the converse, suppose \(M\) is not maximum. There is then a matching \(N\) with \(|N|>|M|\). Form the symmetric difference \(M\mathbin{\triangle}N\), consisting of edges in exactly one of \(M,N\). In the graph formed by these edges, every vertex has degree at most \(2\), because each of \(M\) and \(N\) contributes at most one incident edge. Moreover, at any vertex of degree \(2\), one incident edge belongs to \(M\setminus N\) and the other to \(N\setminus M\). Thus each nontrivial connected component is an alternating path or an alternating cycle. On an alternating cycle the numbers of \(M\)-edges and \(N\)-edges are equal. On an alternating path they differ by at most one. Since \(N\) has more edges overall, at least one path component has one more \(N\)-edge than \(M\)-edge. Its first and last edges belong to \(N\setminus M\). Each endpoint is unsaturated by \(M\): if an endpoint had an incident \(M\)-edge, that edge could not also be in \(N\), since the endpoint already has an incident \(N\)-edge; it would therefore occur in the symmetric difference and contradict that the endpoint of the component has degree \(1\). This component is a positive-length alternating path with both endpoints unsaturated by \(M\), hence an augmenting path. Therefore, if no augmenting path exists, \(M\) must be maximum. \(\square\)
Worked Example: Check Both Endpoints
Worked Example: An Alternating Path That Is Not Augmenting
Let \(G=(V,E)\) have parts \(\{1,3\}\) and \(\{2\}\), with \(V=\{1,2,3\}\), \(E=\{12,23\}\), and \(M=\{12\}\). The path \(1,2,3\) alternates: \(12\) is in \(M\) and \(23\) is outside \(M\). But vertex \(1\) is saturated by \(12\), while vertex \(3\) is unsaturated. The path is not augmenting because both endpoints must be unsaturated.
If one incorrectly flips this path, the result is \(\{23\}\): remove \(12\), add \(23\), and the size remains \(1\). This is a valid matching, but it is not an augmentation. In contrast, in the previous example both endpoints were unsaturated, and flipping increased the size from \(1\) to \(2\).
Check: The two possible one-edge matchings are \(\{12\}\) and \(\{23\}\), and neither can be enlarged because the two graph edges share vertex \(2\). Both are maximum of size \(1\). The path above therefore cannot be used to infer that \(M\) was not maximum.
A related endpoint error is to allow a single isolated vertex to count as an augmenting path for the empty matching. A one-vertex path has length \(0\); it has no edge to flip, and flipping it cannot increase the matching. The positive-length condition rules out this false conclusion. In a graph with no edges, the empty matching is maximum and there is no augmenting path under the stated definition.
Vertex Covers Are Not Edge Covers
The inequalities and certificates in bipartite matching arguments use vertex covers, not edge covers. A matching and a vertex cover give a basic size comparison: each edge of the matching must meet the cover, and distinct matching edges require distinct cover vertices. An edge cover has a different purpose: its edges collectively touch every vertex.
Proof. Every edge of \(M\) has at least one endpoint in \(C\), since \(C\) covers every edge. Choose one such endpoint for each edge of \(M\). Different edges of \(M\) have disjoint endpoints because \(M\) is a matching, so the chosen vertices are all distinct. Therefore \(|M|\le |C|\). Now suppose \(|M|=|C|\). For any matching \(N\), the same inequality gives \(|N|\le |C|=|M|\), so \(M\) is maximum. For any vertex cover \(D\), it gives \(|M|\le |D|\), so \(|C|\le |D|\) and \(C\) is minimum. These arguments also apply when \(M\) and \(C\) are empty. \(\square\)
This proposition explains why a matching and a vertex cover of equal size certify optimality. It does not say that an edge cover of the same size gives such a certificate. If a graph has an isolated vertex, it has no edge cover at all, because no edge can be incident with that vertex.
Worked Example: One Set Covers Edges, the Other Covers Vertices
Let \(G=(V,E)\) be the path with \(V=\{1,2,3,4\}\) and \(E=\{12,23,34\}\). The vertex set \(\{2,3\}\) is a vertex cover: edge \(12\) meets \(2\), edge \(23\) meets both \(2\) and \(3\), and edge \(34\) meets \(3\). It has size \(2\).
The edge set \(\{12,34\}\) is an edge cover: vertex \(1\) is incident with \(12\), vertex \(2\) with \(12\), vertex \(3\) with \(34\), and vertex \(4\) with \(34\). It also has size \(2\), but it does not cover every edge: \(23\notin\{12,34\}\). Treating \(\{12,34\}\) as a vertex cover is a type error, because it is a set of edges, not a set of vertices.
For an optimality certificate, take the matching \(M=\{12,34\}\) and the vertex cover \(C=\{2,3\}\). Both have size \(2\), so the proposition proves that \(M\) is maximum and \(C\) is minimum. Independently, a matching in this graph has at most two edges because there are only four vertices and each matching edge uses two distinct vertices; the displayed matching attains that bound.
Check: The middle edge \(23\) is covered by the vertex set \(C\), since both its endpoints are in \(C\), but it is not in the edge set \(\{12,34\}\). Conversely, the edge cover touches all four vertices. The two sets satisfy different definitions despite having the same size.
A Short Checklist for Matching Arguments
Before accepting a matching argument, check which claim its reasoning actually supports. If no edge can be added while keeping the current matching, the conclusion is maximal, not necessarily maximum. To show maximum by the augmenting-path criterion, rule out every augmenting path, or exhibit a vertex cover of the same size as the matching. To claim an augmentation, verify that the path has positive length, alternates with respect to the matching, and has two unsaturated endpoints. When flipping, remove the matched path edges and add the unmatched path edges. Finally, check whether a proposed cover is a set of vertices covering edges or a set of edges incident with every vertex.
Check Your Understanding
For each question, identify the definition or certificate that applies before drawing a conclusion.
- In the graph with \(V=\{1,2,3,4\}\) and \(E=\{12,23,34\}\), why is \(\{23\}\) maximal but not maximum?
- Can a length-zero path be an augmenting path under the definition in this tutorial? Explain what would go wrong if it were allowed.
- For an augmenting path of length \(7\), how many of its edges belong to \(M\), and how many are added when it is flipped?
- In the graph with \(V=\{1,2,3,4\}\) and \(E=\{12,23,34\}\), which property does \(\{12,34\}\) have: vertex cover, edge cover, or both? Justify your answer.
- Why does a matching and a vertex cover of equal size certify that the matching is maximum, whereas equality with the size of an edge cover does not establish that conclusion?