Recipe

Prove a matching is maximum with a vertex cover

Use when: you already have a specific matching and need to show no larger one exists, without an exhaustive search

Goal: a matching-size vertex cover that certifies the matching is maximum, or the recognition that this test alone cannot decide the question

Taught in Matching, revisited

Quick recipe

Note the matching's size
Search for a vertex cover of that same size
Verify the candidate cover touches every edge
Interpret what the outcome proves

1
Note the size $k$ of the matching $M$ you already have; call it the target. You want to show no matching in this graph can beat size $k$ , without checking every alternative by hand.

Example

On the 4-cycle $a\text{-}b\text{-}c\text{-}d\text{-}a$ , take $M=\{ab, cd\}$ . Both edges are disjoint, so $M$ is a matching and $k=2$ .

Why: the whole point is to pin $k$ down as a hard ceiling, not just a large matching you happened to find.
2
Look for a set of exactly $k$ vertices that touches every edge of the graph. Try vertices that already show up often among the matched edges first.

Example

On the same 4-cycle, try $C=\{a,c\}$ : both are matched vertices, and $|C|=k=2$ .

Why: only a cover of size exactly $k$ , not a bigger one, can pin the maximum matching down to $k$ .
3
Check every single edge of the graph against your candidate cover $C$ , one edge at a time. A cover that misses even one edge does not count.

Example

The 4-cycle has edges $ab, bc, cd, da$ . Check each: $ab$ touches $a$ , $bc$ touches $c$ , $cd$ touches $c$ , $da$ touches $a$ . All four edges touch $C=\{a,c\}$ , so $C$ is a genuine cover of size $2$ .

Why: an unchecked "cover" that actually misses an edge proves nothing at all.
4
Compare the cover size you actually found to $k$ , then read off what that comparison proves about the matching.
- you found a cover of size exactly $k$ — $M$ is proven maximum, since $k\leq \min_C|C|\leq k$ forces equality
- no size- $k$ cover turned up after a real search — this test alone is inconclusive, a genuine gap may exist
Why: the inequality from the technical box only cuts one way, so a matched cover is proof but a missing one is not disproof.

Common mistakes

Reporting a cover of some size without checking it is exactly $k$ ; a bigger cover proves nothing new.
Concluding a matching is not maximum just because no size- $k$ cover turned up; the gap can be genuine, as an odd cycle shows.
Counting vertices instead of checking every edge, and missing an edge the proposed cover never actually touches.
Assuming a vertex cover can always be built straight from the matched vertices; that guess can fail on general graphs.