Matchings & Vertex Covers

Augmenting paths, weak duality, and König's theorem.

The idea

A matching in a graph is a set of edges no two of which share a vertex, so it pairs off some of the vertices. A maximum matching contains as many edges as possible, and that number of edges is the matching number $\nu(G)$. A vertex cover is a set of vertices containing at least one endpoint of every edge, and the fewest vertices in any vertex cover is the covering number $\tau(G)$.

The two numbers constrain each other.

Lemma (Weak duality).

In every graph $G$, $\nu(G) \le \tau(G)$.

Take any matching and any vertex cover. The cover contains an endpoint of each matching edge, and since matching edges share no vertices, those endpoints are all distinct — so the cover has at least as many vertices as the matching has edges. The inequality can be strict: a triangle has $\nu = 1$ and $\tau = 2$.

Theorem (König's theorem).

If $G$ is bipartite — its vertices split into two parts with every edge running between the parts — then $\nu(G) = \tau(G)$.

Ways to work on it

• Walkthrough. Matching number, vertex cover, and augmenting paths.
• Practice. Find the matching number of a small bipartite graph.
• Hardest. Certify a maximum matching with a minimum vertex cover.

Not sure where to start? Take the ten-question placement test.