Solving the Three Problems Together
In a bipartite graph, finding a large matching, a small vertex cover, and a large independent set are closely connected tasks. Instead of treating them as three separate searches, we can solve them together and use the results to check one another. A matching provides a lower bound on the size of every vertex cover, while a vertex cover provides an upper bound on the size of every matching. When those bounds agree, both sets are optimal. The complement of a minimum vertex cover then gives a maximum independent set.
Throughout, graphs are finite and simple. A bipartite graph \(G=(V,E)\) has a specified bipartition \(L,R\): these sets are disjoint, their union is \(V\), and every edge has one endpoint in each. A matching is a set of edges with no shared endpoints. A maximum matching has largest size among all matchings; a maximal matching is one to which no edge can be added. These terms are different: a maximal matching need not be maximum.
A useful certificate of optimality is a matching and a vertex cover of the same size. Every edge of a matching must be covered, and distinct matching edges have disjoint endpoints. Therefore every vertex cover has at least as many vertices as any matching:
Thus, if a matching \(M\) and a vertex cover \(C\) have equal size, \(M\) is maximum and \(C\) is minimum. Their common size is the matching number and the vertex cover number. This comparison works in every graph; in bipartite graphs, Kőnig’s matching-cover theorem guarantees equality between the maximum matching size and the minimum cover size.
Alternating Reachability Gives a Cover
Here is a constructive way to obtain a minimum cover from a maximum matching \(M\). Start at every unmatched vertex in \(L\). From a reached vertex of \(L\), follow edges not in \(M\) to \(R\); from a reached vertex of \(R\), follow its matching edge, if it has one, back to \(L\). Let \(Z_L\) and \(Z_R\) be the reached vertices in the two parts. The routes alternate between edges outside \(M\) and edges in \(M\).
Proof. Berge’s theorem states that a matching is maximum if and only if there is no augmenting path for it; an augmenting path is a path whose edges alternate between edges outside and inside the matching and whose two endpoints are unmatched. Since \(M\) is maximum, no unmatched vertex of \(R\) is reachable from an unmatched vertex of \(L\). Otherwise the alternating route to it would be an augmenting path. Thus every vertex in \(Z_R\) is matched.
We first show that \(C\) covers every edge \(uv\), where \(u\in L\) and \(v\in R\). If \(u\notin Z_L\), then \(u\in C\). If \(u\in Z_L\) and \(uv\notin M\), the reachability rule from \(L\) gives \(v\in Z_R\), so \(v\in C\). If \(u\in Z_L\) and \(uv\in M\), then \(u\) cannot be an unmatched starting vertex. It was reached along its matching edge, so \(v\in Z_R\) and again \(v\in C\). These cases cover every edge.
Every matched edge either has both endpoints reached or has neither endpoint reached: reaching its \(R\)-endpoint leads across that matching edge to its \(L\)-endpoint, and reaching its \(L\)-endpoint (which is matched) entails that its matching \(R\)-endpoint was reached. In the first case its \(R\)-endpoint lies in \(C\); in the second case its \(L\)-endpoint lies in \(C\). Unmatched vertices of \(L\) are reached and unmatched vertices of \(R\) are not reached, so neither contributes an extra vertex to \(C\). Consequently \(C\) contains exactly one endpoint of each matching edge and no unmatched vertices. Hence \(|C|=|M|\). The matching-cover inequality now shows that \(M\) is maximum and \(C\) is minimum. \(\square\)
Complements connect covers and independent sets. For any graph, \(C\) is a vertex cover if and only if \(V\setminus C\) is an independent set: an edge with both endpoints outside \(C\) is exactly an edge with both endpoints in \(V\setminus C\). Taking complements reverses set size, so a minimum cover has a maximum independent-set complement. In particular, if \(n=|V|\), then \(\alpha(G)=n-\tau(G)\), where \(\alpha(G)\) is the maximum independent-set size and \(\tau(G)\) is the minimum vertex-cover size.
Worked Problems
Worked Example: A Matching, Cover, and Independent Set
Let \(L=\{a,b,c,d\}\), \(R=\{1,2,3\}\), and let \(E=\{a1,a2,b1,b3,c2,d2,d3\}\). Find a maximum matching, a minimum vertex cover, and a maximum independent set.
Build a matching by adding disjoint edges. Start with \(M_0=\varnothing\). Add \(a1\) to obtain \(M_1=\{a1\}\), then \(b3\) to obtain \(M_2=\{a1,b3\}\), and then \(c2\) to obtain \(M_3=\{a1,b3,c2\}\). These edges have distinct endpoints, so \(M_3\) is a matching of size \(3\). Vertex \(d\) is unmatched.
For the reachability check, start at \(d\). Its nonmatching edges reach \(2\) and \(3\). Their matching edges reach \(c\) and \(b\). From \(b\), the nonmatching edge \(b1\) reaches \(1\), whose matching edge reaches \(a\). Thus \(Z_L=\{a,b,c,d\}\) and \(Z_R=\{1,2,3\}\). The construction gives \(C=(L\setminus Z_L)\cup Z_R=\{1,2,3\}\).
Every listed edge has its right endpoint in \(C\), so \(C\) is a cover. Its size is \(3\), equal to \(|M_3|=3\); the matching-cover inequality certifies that the matching is maximum and the cover is minimum. The complement of \(C\) is \(I=\{a,b,c,d\}\). No two vertices of \(I\) are adjacent because all edges go from \(L\) to \(R\). Here \(|V|=4+3=7\), and \(|I|=4=7-3\), so the complement has the size required for a maximum independent set.
Check: The matching uses \(a,b,c\) and \(1,2,3\), each exactly once. The cover includes every right vertex, so it covers all seven listed edges. The independent set contains all four left vertices and no right vertices, so no edge has both endpoints in it.
Worked Example: A Minimum Cover Using Both Parts
Let \(L=\{a,b,c,d\}\), \(R=\{1,2,3\}\), and \(E=\{a1,b1,b2,c2,d3\}\). Find optimal sets and verify their sizes.
Take \(M=\{a1,b2,d3\}\). Its edges have distinct endpoints, so it is a matching of size \(3\). To trace how the matching can be found, first take \(a1\), then add \(b2\), and then add \(d3\). The remaining left vertex \(c\) is unmatched.
Start alternating reachability at \(c\). The nonmatching edge \(c2\) reaches \(2\), and the matching edge \(b2\) reaches \(b\). From \(b\), the nonmatching edge \(b1\) reaches \(1\), and the matching edge \(a1\) reaches \(a\). Thus \(Z_L=\{a,b,c\}\) and \(Z_R=\{1,2\}\). The resulting cover is \(C=(L\setminus Z_L)\cup Z_R=\{d,1,2\}\).
Check each edge: \(a1\) and \(b1\) are covered by \(1\); \(b2\) and \(c2\) are covered by \(2\); and \(d3\) is covered by \(d\). The cover has size \(3\), equal to the matching size, so both are optimal.
The complementary independent set is \(I=V\setminus C=\{a,b,c,3\}\). None of the edges \(a1,b1,b2,c2,d3\) has both endpoints in \(I\), so \(I\) is independent. There are \(7\) vertices, and \(|I|=4=7-3\). Therefore \(I\) is maximum.
Check: The equality \(|M|=|C|=3\) provides the optimality certificate, and the complement calculation gives \(|I|=|V|-|C|=7-3=4\).
Worked Example: Augmenting Before Certifying
Let \(L=\{p,q,r,s\}\), \(R=\{1,2,3,4\}\), and \(E=\{p1,p2,q1,r2,s3\}\). Find a maximum matching, a minimum cover, and a maximum independent set. Vertex \(4\) is isolated.
Start with \(M_0=\{p1,s3\}\). The path \(q,1,p,2\) alternates: \(q1\notin M_0\), \(1p\in M_0\), and \(p2\notin M_0\). It starts at the unmatched vertex \(q\) and ends at the unmatched vertex \(2\). Flip membership along this path: remove \(p1\) and add \(q1,p2\). The result is \(M_1=\{q1,p2,s3\}\), a matching of size \(3\). Vertex \(r\) is unmatched.
Start reachability at \(r\). The nonmatching edge \(r2\) reaches \(2\); the matching edge \(2p\) reaches \(p\). From \(p\), the nonmatching edge \(p1\) reaches \(1\), and the matching edge \(1q\) reaches \(q\). No further left or right vertices are reached. Hence \(Z_L=\{p,q,r\}\) and \(Z_R=\{1,2\}\), giving \(C=\{s,1,2\}\).
The edges \(p1,q1\) meet \(1\), \(p2,r2\) meet \(2\), and \(s3\) meets \(s\). So \(C\) covers every edge and \(|C|=3=|M_1|\). The matching is maximum and the cover minimum. The complement is \(I=\{p,q,r,3,4\}\). None of the listed edges has both endpoints in \(I\), so it is independent. There are \(8\) vertices, and \(8-3=5=|I|\); therefore it is maximum. The isolated vertex \(4\) belongs to the maximum independent set and causes no change to the matching or cover.
Check: The augmentation replaces one matching edge by two, so the size changes from \(2\) to \(2-1+2=3\). The final matching and cover both have size \(3\), and the independent set has size \(8-3=5\).
Common Pitfalls and a Reliable Checklist
A common mistake is to call any matching that cannot be enlarged by adding a single edge “maximum.” That condition defines a maximal matching, not a maximum one. For instance, in the third example, \(\{p1,s3\}\) is maximal: each remaining edge touches a vertex already used. But it is not maximum, because the alternating path \(q,1,p,2\) increases its size from \(2\) to \(3\). The correction is to search for augmenting paths, or to certify the claimed size with a vertex cover of the same size.
Another tempting but wrong calculation is to take the complement of a maximum matching as a maximum independent set. In the first example, the matching has three edges, so its set of endpoints is \(\{a,b,c,1,2,3\}\), and that set’s complement is \(\{d\}\). But the maximum independent set is \(\{a,b,c,d\}\), of size \(4\). A matching is a set of edges, not a vertex cover: its endpoints need not cover every edge. The correct complement operation is to take the complement of a vertex cover.
For an explicit problem, write down the bipartition and the entire edge set first. Then build a matching, checking that no endpoints repeat; use augmenting paths to improve it if needed. From a maximum matching, perform alternating reachability and form \((L\setminus Z_L)\cup Z_R\). Finally, check every edge against the cover, compare cover and matching sizes, and take the cover’s complement to obtain an independent set. Verify that no edge has both endpoints in that set and that its size is \(|V|-|C|\).
Check Your Understanding
For each problem, identify the sets and verify the relevant properties rather than relying only on a proposed answer.
- In the graph with \(L=\{u,v,w\}\), \(R=\{1,2\}\), and \(E=\{u1,v1,v2,w2\}\), find a maximum matching, a minimum vertex cover, and a maximum independent set.
- Explain why a matching and a vertex cover of equal size certify that both are optimal.
- For the graph in Question 1, start alternating reachability from every unmatched left vertex and calculate \(Z_L\), \(Z_R\), and the resulting cover.
- Give an example of a vertex that belongs to a maximum independent set but to no matching edge, and explain why this causes no contradiction.
- Why does taking the complement of a vertex cover produce an independent set, while taking the complement of a matching’s endpoint set does not generally produce a maximum independent set?