The Matching–Cover Inequality
A matching consists of edges that do not share endpoints. A vertex cover, by contrast, is a set of vertices that meets every edge. These conditions connect the two objects: if several edges in a matching must each be met by a cover, the cover needs enough vertices to meet them separately. The resulting bound applies to every finite simple graph, whether or not the graph is bipartite.
“At least one endpoint” is important: a cover is allowed to contain both endpoints of an edge, but it does not have to. Also, a matching need not meet every vertex. Vertices not used by its edges may remain unmatched. Since the graph is finite, there are only finitely many subsets of edges and vertices; therefore a largest matching and a smallest vertex cover exist.
Proof. For each edge \(e\in M\), choose one endpoint \(c_e\) that belongs to \(C\). Such an endpoint exists because \(C\) covers every edge. If \(e\) and \(f\) are distinct edges in \(M\), they have no common endpoint, since \(M\) is a matching. Consequently \(c_e\ne c_f\). Thus the choices assign a different vertex of \(C\) to each edge of \(M\). There are \(|M|\) chosen vertices, all distinct and all in \(C\), so \(|M|\le |C|\). If \(M=\varnothing\), the inequality reads \(0\le |C|\), which holds because a set has nonnegative size. \(\square\)
The proof uses only the fact that matching edges are pairwise disjoint and that the cover meets every edge. In particular, it does not rely on a bipartition. It also does not say that every vertex in \(C\) must be used by the choices: a cover may contain extra vertices or may include both endpoints of some matching edge.
From Individual Choices to Graph Parameters
The theorem applies to every particular matching and every particular cover. Choosing a largest matching and a smallest cover gives the corresponding inequality for the graph’s parameters.
Proof. Choose a matching \(M\) of maximum size and a vertex cover \(C\) of minimum size; these exist because \(G\) is finite. By the definitions, \(|M|=\nu(G)\) and \(|C|=\tau(G)\). Applying the theorem to this \(M\) and \(C\) gives \(\nu(G)\le\tau(G)\). If \(G\) has no edges, the empty matching has size \(0\), the empty set is a vertex cover of size \(0\), and the same inequality holds. Isolated vertices do not affect the argument: they are not endpoints of any edge that must be covered. \(\square\)
One way to read this result is as a lower bound: finding a matching of size \(k\) proves that every vertex cover has size at least \(k\). The inequality by itself is one-sided. For a particular graph, it may be strict, so it does not say that a cover of size \(\nu(G)\) always exists.
Worked Example: A Triangle Gives a Strict Inequality
Let \(G=(V,E)\) be the simple graph with \(V=\{a,b,c\}\) and \(E=\{ab,bc,ca\}\). Take \(M=\{ab\}\) and \(C=\{a,b\}\).
The set \(M\) is a matching with \(|M|=1\), because it has just one edge. The set \(C\) is a vertex cover: \(ab\) meets \(C\) at both endpoints, \(bc\) meets it at \(b\), and \(ca\) meets it at \(a\). Its size is \(|C|=2\). Thus the theorem gives \(1\le2\).
In fact, \(\nu(G)=1\). Any two distinct edges of the triangle share a vertex, so a matching cannot contain two edges; the displayed one-edge matching shows that size \(1\) is attainable. Also \(\tau(G)=2\): no single vertex covers the edge opposite it, while \(\{a,b\}\) is a cover of size \(2\). Hence \(\nu(G)=1<2=\tau(G)\).
Check: the matching edge \(ab\) is met by \(a\in C\) (or by \(b\in C\)). This assigns one distinct cover vertex to the one matching edge. The fact that the cover has a second vertex does not violate the bound.
Worked Example: A Four-Vertex Path Gives Equality
Let \(G=(V,E)\) have \(V=\{1,2,3,4\}\) and \(E=\{12,23,34\}\). Choose \(M=\{12,34\}\) and \(C=\{2,3\}\).
The edges \(12\) and \(34\) have no common endpoints, so \(M\) is a matching and \(|M|=2\). To check \(C\), inspect every edge: \(12\) meets \(C\) at \(2\), \(23\) meets it at both \(2\) and \(3\), and \(34\) meets it at \(3\). Thus \(C\) is a vertex cover with \(|C|=2\).
These sizes are optimal. A matching of size \(r\) uses \(2r\) distinct vertices, so in this graph \(2r\le4\), which gives \(r\le2\). The displayed matching therefore gives \(\nu(G)=2\). The theorem applied to that matching says every vertex cover has size at least \(2\); the displayed cover has size \(2\), so \(\tau(G)=2\).
Check: the choices \(12\mapsto2\) and \(34\mapsto3\) are distinct vertices of \(C\), one for each matching edge. Substitution into the inequality gives \(|M|=2\le2=|C|\), with equality.
Worked Example: An Isolated Vertex Does Not Change the Bound
Let \(G=(V,E)\) have \(V=\{a,b,c,d,e,f\}\) and \(E=\{ab,bc,de\}\). The vertex \(f\) is isolated. Take \(M=\{ab,de\}\) and \(C=\{b,d\}\).
The two edges in \(M\) are disjoint, so \(M\) is a matching of size \(2\). For the cover check, \(ab\) meets \(C\) at \(b\), \(bc\) meets \(C\) at \(b\), and \(de\) meets \(C\) at \(d\). Therefore \(C\) is a cover of size \(2\). The isolated vertex \(f\) is not incident to an edge, so it creates no additional condition for a vertex cover.
There are only three edges. The two edges \(ab\) and \(bc\) share \(b\), so at most one of them can be used in a matching; the edge \(de\) can contribute at most one more. Hence every matching has size at most \(2\), and the displayed matching shows \(\nu(G)=2\). The theorem gives \(\tau(G)\ge2\), while the displayed cover gives \(\tau(G)\le2\). Consequently \(\tau(G)=2\).
Check: here the matching edges \(ab\) and \(de\) are assigned the distinct cover vertices \(b\) and \(d\). The vertex \(c\) is covered by \(b\) through edge \(bc\), and the isolated vertex \(f\) needs no cover vertex.
Why the Disjointness Condition Matters
The proof depends on being able to assign different cover vertices to different matching edges. Disjoint matching edges guarantee that no vertex can serve as an endpoint of two of those edges. Without the matching condition, the selection argument can fail: one cover vertex might meet several edges, and counting one chosen endpoint per edge would then count that same vertex repeatedly.
For example, in the triangle above, the set \(\{ab,bc\}\) is not a matching because both edges contain \(b\). A mistaken calculation might call it a matching of size \(2\) and compare it with the cover \(\{b\}\) of size \(1\), apparently contradicting the inequality. The correction is that the two edges share \(b\), so they cannot both belong to a matching. The largest matching in that triangle has size \(1\), and the valid comparison is \(1\le2\) for the cover \(\{a,b\}\), or \(1\le1\) for the cover \(\{b,c\}\).
There is a related counting mistake in the other direction: the theorem requires at least one cover vertex per matching edge, not two. A cover does not have to include both endpoints of every edge. In the star with vertices \(\{x,a,b,c\}\) and edges \(\{xa,xb,xc\}\), the single vertex set \(C=\{x\}\) covers all three edges. Each edge is met at \(x\), but a matching can use at most one of the edges because all three share \(x\). Thus a matching such as \(M=\{xa\}\) has size \(1\), and the bound is \(1\le1\), not a requirement that the cover have size at least \(2\).
The inequality is useful whenever a matching is known: it supplies a lower bound on the size of every cover, without requiring a search through all covers. Conversely, a cover and a matching can be checked using their definitions: the matching edges must be pairwise disjoint, and each edge must have an endpoint in the cover. Keeping those two conditions separate prevents the common error of counting a collection of intersecting edges as a matching.
Check Your Understanding
For each question, state which matching or cover condition justifies the comparison.
- In the graph \(V=\{1,2,3,4,5\}\), \(E=\{12,23,34,45\}\), take \(M=\{12,34\}\) and \(C=\{2,4\}\). Verify that \(M\) is a matching and \(C\) is a cover, then compare their sizes.
- Explain why two edges in a matching cannot be assigned the same endpoint when proving the matching–cover inequality.
- In the triangle with edges \(\{ab,bc,ca\}\), why is \(\{ab,bc\}\) not a matching, even though it is a set of two edges?
- Give a reason the inequality still applies when a graph has isolated vertices.
- Does the inequality \(\nu(G)\le\tau(G)\) alone assert that \(\nu(G)=\tau(G)\)? Explain what the theorem proves and what it does not prove.