From a Maximum Matching to a Cover
A matching pairs vertices without using any vertex more than once; a vertex cover meets every edge. In a bipartite graph, a maximum matching can guide us to a cover of the same size. The key is to follow alternating routes from vertices in one part that the matching leaves unmatched. The vertices reached by this search tell us which vertices to include on each side of the bipartition.
All graphs in this tutorial are finite and simple. A bipartite graph \(G=(V,E)\) has a vertex partition \(V=X\cup Y\), where \(X\cap Y=\varnothing\), such that every edge has one endpoint in \(X\) and one in \(Y\). A matching \(M\subseteq E\) is a set of pairwise vertex-disjoint edges, and it is maximum if no matching in \(G\) has more edges. A vertex cover is a set \(C\subseteq V\) containing at least one endpoint of every edge. We use the earlier material on matchings and alternating paths: an edge not in \(M\) is unmatched, and an edge in \(M\) is matched.
The directions are part of the definition: from \(X\) to \(Y\) use only unmatched edges, and from \(Y\) to \(X\) use only matched edges. Vertices unmatched in \(X\) are all starting points, including isolated vertices. A search can be carried out separately in each component it reaches; components with no unmatched vertex in \(X\) contribute no reachable vertices.
Why the Construction Works
Proof. First, no vertex of \(Z_Y\) can be unmatched by \(M\). If an unmatched \(y\in Y\) were reached, a shortest directed route in the search from an unmatched vertex of \(X\) to \(y\) would have no repeated vertices. It would be an alternating path beginning and ending with unmatched vertices. Replacing its unmatched edges by matched edges, and its matched edges by unmatched edges, would increase the size of \(M\) by one: the path has one more unmatched edge than matched edge, and the switch preserves the matching condition. This contradicts maximal size. Thus every vertex of \(Z_Y\) is matched.
We next show that every edge has an endpoint in \(C\). Suppose an edge \(xy\), with \(x\in X\) and \(y\in Y\), has neither endpoint in \(C\). Then \(x\in Z_X\) and \(y\notin Z_Y\). If \(xy\notin M\), the search rule from \(x\) would reach \(y\), a contradiction. If \(xy\in M\), then \(x\) is not an unmatched starting vertex. Since \(x\) is reached, it must have been reached from its matched partner in \(Y\); the only matched edge by which the search enters \(x\) is \(xy\). Hence \(y\in Z_Y\), again a contradiction. Therefore \(C\) is a vertex cover.
To count \(C\), observe that each vertex of \(Z_Y\) is matched, and its partner in \(X\) is reached by the search. Conversely, every matched vertex in \(Z_X\) was reached from its matched partner in \(Z_Y\). Thus the matched vertices of \(Z_X\) are in one-to-one correspondence with \(Z_Y\). The remaining vertices of \(Z_X\) are exactly the unmatched vertices of \(X\), all of which were starting points. If their number is \(r\), then \(|Z_X|=|Z_Y|+r\). The matching saturates exactly \(|X|-r\) vertices of \(X\), so \(|M|=|X|-r\). It follows that \[ |C|=|X|-|Z_X|+|Z_Y|=|X|-r=|M|. \]
Finally, any vertex cover must contain at least one endpoint of each edge of \(M\). Because the matching edges are pairwise vertex-disjoint, these requirements require at least \(|M|\) distinct cover vertices. We have constructed a cover of size \(|M|\), so no smaller cover exists. This also covers the empty matching: if \(M=\varnothing\) is maximum, there are no edges, the constructed set is empty, and it is a minimum cover. \(\square\)
Tracing the Search
A queue is a convenient way to implement the search: put all unmatched vertices of \(X\) in the queue, remove one reached vertex at a time, and add any newly reached neighbors according to the traversal rules. Keep track of which vertices have already been reached so that none is processed twice. The queue records the search, but the cover is formed only after both reachable sets are known.
Worked Example: Every Vertex Is Reached
Let \(G=(X\cup Y,E)\), where \(X=\{a,b,c,d\}\), \(Y=\{1,2,3\}\), and \(E=\{a1,a2,b1,b2,c2,c3,d3\}\). Take \(M=\{a1,b2,c3\}\). This matching is maximum: it has three edges, and any matching has at most \(|Y|=3\) edges. The only unmatched vertex in \(X\) is \(d\).
Start with \(d\). The search proceeds as follows; the queue is shown after processing each vertex.
| Processed vertex | New vertices reached | Queue afterward |
|---|---|---|
| Start | \(d\) | \(d\) |
| \(d\in X\) | \(3\), via unmatched edge \(d3\) | \(3\) |
| \(3\in Y\) | \(c\), via matched edge \(c3\) | \(c\) |
| \(c\in X\) | \(2\), via unmatched edge \(c2\) | \(2\) |
| \(2\in Y\) | \(b\), via matched edge \(b2\) | \(b\) |
| \(b\in X\) | \(1\), via unmatched edge \(b1\) | \(1\) |
| \(1\in Y\) | \(a\), via matched edge \(a1\) | \(a\) |
| \(a\in X\) | None new; \(a2\) leads to already reached \(2\) | empty |
Thus \(Z_X=\{a,b,c,d\}\) and \(Z_Y=\{1,2,3\}\). The formula gives \(C=(X\setminus Z_X)\cup Z_Y=\{1,2,3\}\), of size \(3\). Every edge has an endpoint in \(Y=\{1,2,3\}\), so this is a cover. Its size equals \(|M|=3\); the theorem confirms it is minimum. Independently, the three disjoint matching edges require at least three cover vertices.
Worked Example: The Cover Uses Both Parts
Let \(X=\{a,b,c,d\}\), \(Y=\{1,2,3\}\), and \(E=\{a1,b1,b2,c2,d3\}\). Use \(M=\{a1,b2,d3\}\). It is maximum because it has three edges and there are only three vertices in \(Y\). The unmatched vertex of \(X\) is \(c\).
From \(c\), traverse the unmatched edge \(c2\), reaching \(2\). From \(2\), traverse the matched edge \(b2\), reaching \(b\). From \(b\), traverse the unmatched edge \(b1\), reaching \(1\). From \(1\), traverse the matched edge \(a1\), reaching \(a\). There are no further new vertices: the other edge at \(b\), namely \(b2\), is matched and cannot be traversed from \(X\); \(a\) has no other incident edge. Therefore \(Z_X=\{a,b,c\}\), \(Z_Y=\{1,2\}\).
The construction gives \(C=(X\setminus Z_X)\cup Z_Y=\{d,1,2\}\). Check each edge: \(a1\) is met by \(1\); \(b1\) by \(1\); \(b2\) and \(c2\) by \(2\); and \(d3\) by \(d\). The set has size \(3\), equal to \(|M|=3\). The three disjoint matching edges \(a1,b2,d3\) also show directly that every cover needs at least three vertices, verifying minimality.
Worked Example: An Isolated Starting Vertex
Let \(X=\{a,b,c,d,e\}\), \(Y=\{1,2,3\}\), and \(E=\{a1,b2,c2,d3\}\). Take \(M=\{a1,b2,d3\}\). It is maximum since \(|Y|=3\), and it has three edges. The unmatched vertices in \(X\) are \(c\) and \(e\); \(e\) is isolated.
Initialize the queue with \(c,e\). Processing \(c\) follows the unmatched edge \(c2\), so \(2\) is added. Processing \(e\) adds nothing. Processing \(2\) follows the matched edge \(b2\), so \(b\) is added. Processing \(b\) adds nothing new: its only incident edge is the matched edge \(b2\). The queue is then empty. Hence \(Z_X=\{b,c,e\}\) and \(Z_Y=\{2\}\). The cover is \(C=\{a,d,2\}\). It covers \(a1\) through \(a\), \(b2\) and \(c2\) through \(2\), and \(d3\) through \(d\). Its size is \(3=|M|\), and the three disjoint edges in \(M\) give the matching lower bound of \(3\). The isolated starting vertex is included in \(Z_X\), but it creates no extra cover vertex.
Common Mistakes and the Role of the Method
Using the wrong side of the reachable sets is a common error. In the second example, \(Z_X=\{a,b,c\}\) and \(Z_Y=\{1,2\}\). The correct formula gives \(\{d,1,2\}\). If one instead takes \((X\setminus Z_X)\cup(Y\setminus Z_Y)\), the result is \(\{d,3\}\). This is not a cover: the edge \(a1\) has neither endpoint in \(\{d,3\}\). The correction is to take the complement of the reachable set on the \(X\)-side, but the reachable set itself on the \(Y\)-side.
Another error is to start from matched vertices of \(X\) rather than from all unmatched vertices there. The starting points are what let the search detect possible alternating paths that could improve the matching. Likewise, reversing the traversal rules changes which vertices are reached and invalidates the cover argument: from \(X\), only unmatched edges are followed; from \(Y\), only matched edges are followed.
The construction is useful because it produces an explicit cover, not just its size. In applications, the matching describes a set of disjoint assignments, while the cover identifies a set of vertices touching every possible assignment edge. The alternating search explains how the two structures fit together. It also handles disconnected graphs and isolated vertices without a separate rule: begin at every unmatched vertex of \(X\), and let the prescribed search determine what is reachable.
Check Your Understanding
For each question, state the bipartition and matching assumptions you use.
- In the graph with \(X=\{a,b,c\}\), \(Y=\{1,2\}\), and \(E=\{a1,b1,b2,c2\}\), take \(M=\{a1,b2\}\). Find \(Z_X\), \(Z_Y\), and the constructed cover.
- Why must every vertex of \(Z_Y\) be matched when \(M\) is maximum?
- In the cover proof, explain why a matched edge \(xy\) cannot have \(x\in Z_X\) and \(y\notin Z_Y\).
- Why does every vertex cover have at least \(|M|\) vertices for any matching \(M\)?
- If the graph has no edges, what are the alternating reachable sets and the constructed cover when \(X\) is nonempty?