From a Maximum Matching to a Minimum Cover
A matching selects edges that do not share endpoints. A vertex cover selects vertices that meet every edge. These are different kinds of objects, but in a bipartite graph their optimal sizes agree. The key is to start from a maximum matching and follow alternating edges from its unmatched vertices in one part. The vertices reached by this search determine a cover that is exactly as large as the matching.
All graphs in this tutorial are finite and simple. A matching is a set of pairwise vertex-disjoint edges. A maximum matching has the largest possible number of edges; a maximal matching is one to which no edge can be added while retaining a matching. These terms are not interchangeable. A vertex cover is a set of vertices containing at least one endpoint of every edge. The matching number \(\nu(G)\) is the largest size of a matching, and the vertex cover number \(\tau(G)\) is the smallest size of a vertex cover.
Fix a bipartition \(X,Y\) and a maximum matching \(M\). Begin at every unmatched vertex of \(X\). From a reached vertex in \(X\), follow edges not in \(M\) to vertices in \(Y\). From a reached vertex in \(Y\), follow its matching edge, if it has one, back to \(X\). Call the reached sets \(Z_X\subseteq X\) and \(Z_Y\subseteq Y\). Thus every search path starts at an unmatched vertex of \(X\) and alternates between edges outside and inside \(M\), beginning with an edge outside \(M\).
Why Alternating Reachability Gives the Equality
The cover constructed from the search is $$ C=(X\setminus Z_X)\cup Z_Y. $$ The choice of the two sets is important: vertices of \(X\) not reached are included, while reached vertices of \(Y\) are included.
Proof. Let \(M\) be a maximum matching, and perform the alternating search described above. First, \(C\) is a vertex cover. Suppose an edge \(xy\), with \(x\in X\) and \(y\in Y\), has neither endpoint in \(C\). Then \(x\notin X\setminus Z_X\), so \(x\in Z_X\); also \(y\notin Z_Y\).
If \(xy\notin M\), the search rule allows the search to follow \(xy\) from \(x\) to \(y\). Since \(x\) is reached, this would make \(y\) reached, contradicting \(y\notin Z_Y\). If \(xy\in M\), then \(x\) cannot be an unmatched starting vertex. Any search path reaching \(x\) must enter it along its matching edge: the search enters \(X\) only by following a matching edge from \(Y\). The matching edge incident with \(x\) is \(xy\), so \(y\) must already have been reached. This again contradicts \(y\notin Z_Y\). Thus every edge has an endpoint in \(C\).
Next, no unmatched vertex of \(Y\) is reached. If one were reached, a search path from an unmatched vertex of \(X\) to that unmatched vertex of \(Y\) would be an alternating path whose first and last edges are outside \(M\). A shortest directed search path to that vertex has no repeated vertices, so it is a path. It contains one more edge outside \(M\) than inside \(M\). Replacing the matching edges on this path by the other edges on it produces a matching with one more edge: each internal vertex remains incident with exactly one selected edge, and the two previously unmatched endpoints become matched. This contradicts that \(M\) is maximum.
We now count \(C\). Each matching edge has exactly one endpoint in \(C\). Indeed, for a matching edge \(xy\), if \(y\in Z_Y\), then the search follows its matching edge to \(x\), so \(x\in Z_X\); in this case \(y\in C\) and \(x\notin C\). If \(y\notin Z_Y\), then \(x\notin Z_X\), since a reached \(x\) must have been reached through its matching edge from \(y\). In this case \(x\in C\) and \(y\notin C\). Finally, unmatched vertices are not in \(C\): an unmatched \(x\in X\) is a starting vertex and belongs to \(Z_X\), while an unmatched \(y\in Y\) is not reached, as just proved. Therefore \(C\) consists of exactly one endpoint of each edge in \(M\), and no unmatched vertices. Hence \(|C|=|M|=\nu(G)\).
For any matching \(M'\) and any vertex cover \(C'\), each edge of \(M'\) must have an endpoint in \(C'\). Since the edges of a matching have disjoint endpoints, these require distinct vertices of \(C'\). Thus \(|M'|\le |C'|\), which gives \(\nu(G)\le\tau(G)\). The constructed cover has size \(\nu(G)\), so \(\tau(G)\le\nu(G)\) as well. The two inequalities prove the theorem. If the graph has no edges, the empty matching and empty cover both have size zero, and the equality still holds. \(\square\)
Worked Examples
Worked Example: A Perfect Matching
Let \(G=(V,E)\) have \(X=\{a,c,e\}\), \(Y=\{b,d,f\}\), and edges \(E=\{ab,bc,cd,de,ef\}\). Take \(M=\{ab,cd,ef\}\). These three edges are pairwise disjoint and cover all six vertices, so \(M\) is a perfect matching.
There are no unmatched vertices in \(X\), so the alternating search has no starting vertices. Thus \(Z_X=\varnothing\) and \(Z_Y=\varnothing\), and the constructed cover is \(C=X=\{a,c,e\}\). Check the edges individually: \(ab\) meets \(a\), \(bc\) meets \(c\), \(cd\) meets \(c\), \(de\) meets \(e\), and \(ef\) meets \(e\). Therefore \(C\) is a cover of size \(3\).
Check: The matching has size \(3\), and the cover has size \(3\). The general inequality \(\nu(G)\le\tau(G)\), proved above, rules out a larger matching or a smaller cover. Thus \(\nu(G)=\tau(G)=3\).
Worked Example: One Unmatched Vertex in \(X\)
Let \(G=(V,E)\) have \(X=\{1,2,3\}\), \(Y=\{a,b,c\}\), and edges \(E=\{1a,2a,3b,3c\}\). Use \(M=\{1a,3b\}\). The edges in \(M\) have no common endpoint, and vertex \(2\) is unmatched.
Start at \(2\). The edge \(2a\) is outside \(M\), so reach \(a\); from \(a\), follow its matching edge \(1a\) to \(1\). There are no further vertices to add: \(1\) has no other incident edge, and \(3\) was not reached. The search gives \(Z_X=\{1,2\}\) and \(Z_Y=\{a\}\). Hence \(C=(X\setminus Z_X)\cup Z_Y=\{3\}\cup\{a\}=\{3,a\}\).
Check coverage: the edges \(1a\) and \(2a\) meet \(a\), while \(3b\) and \(3c\) meet \(3\). The cover has size \(2\), equal to the matching size. Moreover, a matching of size \(3\) would require three distinct vertices of \(C\) in any cover, but this cover has only two vertices; equivalently, the proved inequality \(\nu(G)\le\tau(G)\) together with this matching-cover pair certifies that both sizes are \(2\).
Worked Example: A Larger Reachable Set
Let \(G=(V,E)\) have \(X=\{p,q,r,s\}\), \(Y=\{1,2,3,4\}\), and edges \(E=\{p1,p2,q1,q2,r1,r2,s3,s4\}\). Choose \(M=\{p1,q2,s3\}\), a matching of size \(3\). The unmatched vertex in \(X\) is \(r\).
From \(r\), follow the nonmatching edges \(r1\) and \(r2\), reaching \(1\) and \(2\). Follow the matching edge \(1p\) to \(p\), and the matching edge \(2q\) to \(q\). From \(p\), its other incident edge \(p2\) reaches \(2\), already reached; from \(q\), its other incident edge \(q1\) reaches \(1\), already reached. The search stops with \(Z_X=\{r,p,q\}\) and \(Z_Y=\{1,2\}\). The vertex \(s\) is not reached, and neither are \(3\) or \(4\).
The constructed cover is \(C=(X\setminus Z_X)\cup Z_Y=\{s\}\cup\{1,2\}=\{s,1,2\}\). The six edges incident with \(p,q,r\) each meet \(1\) or \(2\); the two edges \(s3,s4\) meet \(s\). So \(C\) is a cover of size \(3\).
Check: \(M\) has size \(3\), and \(C\) has size \(3\). The cover bounds every matching by \(3\), while the displayed matching attains \(3\). Thus \(\nu(G)=\tau(G)=3\), even though \(G\) has eight edges.
Common Pitfall and Why the Construction Matters
A frequent error is to reverse the two pieces of the cover and use \((X\setminus Z_X)\cup(Y\setminus Z_Y)\). In the second example, this gives \(\{3,b,c\}\). The edge \(1a\) has neither endpoint in that set, so it is not a vertex cover. The correct construction uses \(Z_Y\), not \(Y\setminus Z_Y\), because every nonmatching edge leaving a reached vertex of \(X\) leads to a reached vertex of \(Y\).
The theorem gives more than a relationship between two numbers: its proof constructs an optimal cover directly from a maximum matching. It also explains why bipartiteness matters to this argument. The search relies on a fixed division into \(X\) and \(Y\), and on following unmatched edges from \(X\) to \(Y\) and matching edges back. The equality proved here concerns bipartite graphs; it does not assert that matching and vertex-cover numbers are equal in arbitrary graphs.
Check Your Understanding
In each question, identify the matching or cover being used and justify any claim of optimality.
- In the first worked example, why does the absence of unmatched vertices in \(X\) make both reached sets empty?
- For the second graph, list the search steps from the unmatched vertex and verify that \(\{3,a\}\) meets every edge.
- Explain why a reached unmatched vertex of \(Y\) would contradict maximal size of \(M\).
- Why does a matching of size \(k\) and a vertex cover of size \(k\) certify that both are optimal?
- If a bipartite graph has no edges, what are its matching number and vertex cover number?