Matching and Cover Certificates of Optimality

Why Two Objects Can Certify Optimality

Finding a large matching or a small vertex cover can require careful reasoning. Once found, however, their optimality can sometimes be verified with a short comparison. A matching gives a lower bound on the size of every vertex cover, and a vertex cover gives an upper bound on the size of every matching. If the two sizes agree, the bounds meet: neither object can be improved.

All graphs in this tutorial are finite and simple. A matching is a set of edges no two of which share an endpoint. A matching is maximum if it has largest size among all matchings in the graph. A matching is maximal if no edge can be added to it while keeping it a matching; maximal does not necessarily mean maximum. A vertex cover is a set of vertices containing at least one endpoint of every edge. A cover is minimum if it has smallest size among all vertex covers. A bipartite graph is one whose vertices can be partitioned into two sets so that each edge has one endpoint in each set.

These checks use only the proposed matching and cover. They do not require listing all matchings or all vertex covers, which may be numerous. The certificate proves optimality because every matching is bounded above by every cover, as the next result makes precise.

The Certificate Theorem

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\). Distinct edges of \(M\) have disjoint endpoints, by the definition of matching, so the chosen endpoints for distinct edges are distinct vertices. This gives an injection from the edges of \(M\) into the vertices of \(C\), and hence \(|M|\leq |C|\).

Now suppose \(|M|=|C|=k\). For any matching \(M'\), the inequality just proved, applied to \(M'\) and \(C\), gives \(|M'|\leq k=|M|\). Thus no matching is larger than \(M\), so \(M\) is maximum. For any vertex cover \(C'\), applying the same inequality to \(M\) and \(C'\) gives \(k=|M|\leq |C'|\). Thus no cover is smaller than \(C\), so \(C\) is minimum. \(\square\)

The proof gives two bounds that can be used separately: a matching of size \(k\) proves that every cover has size at least \(k\), while a cover of size \(k\) proves that every matching has size at most \(k\). Equal-size certificates meet both bounds at the same integer. Notice that the theorem itself does not require bipartiteness: whenever such a pair is found, it certifies optimality in any finite graph.

Why Bipartite Graphs Have Equal-Size Certificates

A certificate is useful only if an optimal matching and an optimal cover of equal size can be found. For bipartite graphs, Kőnig’s matching-cover theorem guarantees this. In terms of the matching number \(\nu(G)\), the largest size of a matching, and the minimum cover size \(\tau(G)\), the theorem states that \(\nu(G)=\tau(G)\) for every finite bipartite graph. This result was established in the earlier material on Kőnig’s theorem.

Proof. By Kőnig’s theorem, \(\nu(G)=\tau(G)\). Since \(G\) is finite, there is a matching \(M\) of size \(\nu(G)\) and a vertex cover \(C\) of size \(\tau(G)\). Therefore \(|M|=|C|\), so they form a certificate. The same equality shows that any maximum matching and any minimum cover have equal sizes. By the certificate theorem, any such equal-size pair certifies both optima. \(\square\)

This corollary separates two tasks. Kőnig’s theorem guarantees that equal-size optimal objects exist in a bipartite graph; the certificate theorem explains why a particular equal-size pair proves optimality. When checking a proposed pair, the bipartite hypothesis is not needed. It matters for the guarantee that optimal matching and cover sizes agree.

What Unequal Sizes Do—and Do Not—Tell You

If a proposed matching and cover have unequal sizes, they do not form an equal-size certificate. That failure alone does not prove that either proposed object is nonoptimal. The matching may be too small, the cover may be too large, or both may be nonoptimal. In particular, the general inequality \(|M|\leq |C|\) can hold strictly even when both objects are valid.

It is also important not to reverse the certificate theorem. Equal sizes are sufficient for optimality; the theorem does not say that arbitrary valid objects of unequal sizes are optimal. In bipartite graphs, Kőnig’s theorem gives equality for optimal sizes, but it does not make every matching and every cover an optimal pair.

When Equal-Size Certificates Need Not Exist

The graph condition matters for the existence guarantee. The certificate theorem remains true in non-bipartite graphs, but a maximum matching and a minimum cover need not have equal sizes there.

Using Certificates Carefully

To verify a certificate in a worked problem, do not rely only on a drawing or on the impression that the matching is large. Write down the graph’s vertex and edge sets, then check the two structural conditions against the listed edges. Finally, compare the sizes. This gives a finite, auditable argument:

1. For a proposed matching, check that no two selected edges share an endpoint.
2. For a proposed cover, check every edge and identify an endpoint in the cover.
3. Count the selected edges and cover vertices; if the counts agree, invoke the certificate theorem.

The distinction between maximum and maximal is especially relevant. A matching can be maximal because no single unused edge can be added, yet still be smaller than another matching. A cover of the same size as that maximal matching would certify maximum status, but a merely maximal matching does not do so by itself. The cover must actually be checked, and the sizes must agree.

In a bipartite graph, an equal-size pair is both a proof and a concise report of the optimum value: its common size is \(\nu(G)=\tau(G)\). The matching supplies a feasible solution of that size, while the cover rules out every larger matching. In applications, this makes certificates valuable even when the process that found the objects was more involved than their verification.