Matching Lower Bounds for Vertex Covers

Matchings Give Lower Bounds

A matching consists of edges that do not share endpoints. A vertex cover consists of vertices that meet every edge. These are different kinds of objects, but their sizes are linked: each edge in a matching must be met by a different vertex in any vertex cover. This gives a lower bound on the size of every cover. In bipartite graphs the bound is exact: the smallest vertex cover has the same size as the largest matching.

A matching is maximum when its size is as large as possible; this is stronger than being maximal, which means only that no edge can be added to it while keeping a matching. Likewise, a cover can be inclusion-minimal without having the smallest possible size. The bound below compares sizes and applies to every matching and every cover, regardless of whether either is optimal.

Proof. Let \(M\) be a matching and \(C\) a vertex cover. Each edge of \(M\) has at least one endpoint in \(C\), because \(C\) covers every edge. Choose one such endpoint for each edge of \(M\). Since distinct edges of a matching have no common endpoints, the chosen endpoints for distinct edges are distinct vertices. Thus \(C\) contains at least one different vertex for every edge of \(M\), so \(|C|\geq |M|\). Taking \(M\) to be a maximum matching and \(C\) to be a minimum cover gives \(\nu(G)\leq\tau(G)\). If \(E\) is empty, the same reasoning gives \(0\leq |C|\); in particular, it includes the graph with no vertices. \(\square\)

This inequality is useful even when the two optimum sizes are not equal. A matching of size \(k\) proves that every vertex cover has at least \(k\) vertices. To prove that a particular cover is minimum, it is enough to find a matching of the same size: the matching gives the lower bound, and the exhibited cover gives an upper bound.

Equality in Bipartite Graphs

The general lower bound does not by itself guarantee equality. For bipartite graphs, equality follows by building a cover from a maximum matching. The construction uses alternating paths: starting at an unmatched vertex in one part, move across edges not in the matching and back across edges in the matching. The vertices reached in this way determine a cover with exactly one vertex for every matched edge.

Proof. Choose a maximum matching \(M\); a maximum matching exists because a finite graph has only finitely many edge sets. Orient each edge not in \(M\) from \(L\) to \(R\), and orient each edge in \(M\) from \(R\) to \(L\). Let \(Z_L\subseteq L\) and \(Z_R\subseteq R\) be the vertices reachable by directed paths from the unmatched vertices of \(L\). A path of length zero makes every unmatched vertex of \(L\) reachable.

No unmatched vertex of \(R\) can be reachable. Otherwise, a directed path from an unmatched vertex of \(L\) to an unmatched vertex of \(R\) alternates between edges outside \(M\) and edges in \(M\), beginning and ending with edges outside \(M\). The path can be taken simple by deleting any repeated-vertex portions of a directed walk. Replace the matching edges on this path by its non-matching edges. Internal vertices remain incident with exactly one selected edge, the two previously unmatched endpoints become matched, and no vertex outside the path changes. The new matching is larger by one edge, contradicting the maximal size of \(M\).

Now define \(C=(L\setminus Z_L)\cup Z_R\). We show first that \(C\) covers every edge. Suppose an edge \(lr\), with \(l\in L\) and \(r\in R\), were not covered. Then \(l\in Z_L\) and \(r\notin Z_R\). If \(lr\notin M\), its orientation from \(l\) to \(r\) makes \(r\) reachable, a contradiction. If \(lr\in M\), then \(l\) is not an unmatched starting vertex. Every directed path reaching \(l\) must enter it along its matched edge from its matched partner in \(R\); in particular, \(r\in Z_R\), again a contradiction. Thus \(C\) is a vertex cover.

It remains to count \(C\). Every unmatched vertex of \(L\) belongs to \(Z_L\), so it is not in \(C\). No unmatched vertex of \(R\) belongs to \(Z_R\), by the preceding argument, so it is not in \(C\) either. For every matched edge \(lr\), its endpoints are either both reachable or both unreachable: if \(r\) is reachable, its matched edge is directed to \(l\), so \(l\) is reachable; if \(l\) is reachable, it is not a starting vertex and can only be reached through its matched edge, so \(r\) is reachable. When both are reachable, \(C\) contains \(r\) and not \(l\); when both are unreachable, it contains \(l\) and not \(r\). Consequently, \(C\) contains exactly one endpoint from each edge of \(M\) and no unmatched vertices. Hence \(|C|=|M|=\nu(G)\), so \(\tau(G)\leq\nu(G)\). The general lower bound already proves \(\nu(G)\leq\tau(G)\); therefore \(\tau(G)=\nu(G)\). If \(M\) is empty, the same construction gives \(Z_L=L\), \(Z_R=\varnothing\), and \(C=\varnothing\), so the argument also covers that case. \(\square\)

The proof is constructive: once a maximum matching is known, reachability along the oriented edges produces a minimum cover. Isolated vertices cause no difficulty. An isolated vertex in \(L\) that is unmatched is reached but is excluded from \(C\); an isolated vertex in \(R\) is not reached and is also excluded. Neither vertex is needed to cover an edge.

When the Bound Is Strict

Bipartiteness is essential to the equality theorem. In a general graph, a cover may need more vertices than the size of a maximum matching. The lower bound remains valid, but it need not be sharp.

Common Pitfalls

Confusing maximal with maximum. In the triangle, the matching \(\{12\}\) is maximal: neither other edge can be added without sharing an endpoint. It is also maximum, because no matching can have more than one edge. In larger graphs, however, a maximal matching need not be maximum. The lower-bound theorem applies to any matching, but an optimality certificate using the theorem requires a matching whose size reaches the size of the proposed cover.

Assuming equality in every graph. A tempting but incorrect calculation is: “The triangle has a matching of size \(1\), so its minimum vertex cover has size \(1\).” This mistakes a lower bound for an equality. The matching proves only \(\tau(G)\geq1\); the direct check shows that each one-vertex set misses an edge, so the actual value is \(2\). König’s theorem supplies equality under the bipartite hypothesis, not for all graphs.

In practice, matching and cover certificates complement one another. A large matching gives a strong lower bound on cover size; a small cover gives an upper bound. When their sizes agree, both are optimal. In a bipartite graph, the theorem guarantees such equal-size certificates for the two optimum parameters.