4.7Matching and covers
The idea
A matching is a set of edges with no shared vertex; a perfect matching covers every vertex. A vertex cover is a set of vertices touching every edge. In bipartite graphs the biggest matching and the smallest cover are the same size (König).
Think of it like this: Pairing dancers: a matching is a set of dancing couples, and a perfect matching leaves nobody out.
Why it exists
Questions ask for the maximum matching size, perfect matchings of K_{n,n}, and use Hall's condition or König's theorem.
How it works
- ν = maximum matching; τ = minimum vertex cover. König: bipartite ⇒ ν = τ.
- Gallai: α + τ = n (a cover's complement is an independent set).
- Hall: a bipartite graph has a matching saturating side A iff |N(S)| ≥ |S| for every S ⊆ A.
- K_{n,n} has n! perfect matchings; K_{2n} has (2n − 1)!! = (2n−1)(2n−3)…1.
Worked example: Perfect matchings of K₄
(4 − 1)!! = 3·1 = 3: pair 1 with any of 3 others, then the remaining two are forced.
Now play with it
- →Load C₆ and see a perfect matching of size 3.
- →Check α + τ = n in the lab's numbers.
| Result | Statement |
|---|---|
| König | bipartite: maximum matching = minimum vertex cover |
| Gallai | α + τ = n, and ν + minimum edge cover = n (no isolated vertices) |
| Hall | bipartite matching saturates A iff |N(S)| ≥ |S| for all S ⊆ A |
| Perfect matching count | K_{n,n}: n!; K_{2n}: (2n − 1)!! |
| Regular bipartite | a k-regular bipartite graph has a perfect matching |
| Tutte | general graphs: a perfect matching exists iff deleting any vertex set S leaves at most |S| odd components |
A vertex cover and an independent set are complements of each other.
Check yourself
The size of a maximum matching in the Petersen graph (10 vertices) is
Exam notes (the dense version)
A matching has no shared vertices; a perfect matching covers all vertices (n even). ν(G) is the maximum matching size. A vertex cover touches every edge; τ(G) is the smallest. König: in a bipartite graph ν = τ. Gallai: α + τ = n. Hall: a bipartite graph has a matching saturating side A iff |N(S)| ≥ |S| for every S ⊆ A. K_{n,n} has n! perfect matchings; K_{2n} has (2n−1)!! of them.
Previous year questions: Graph Theory (24)
PYQs are grouped by topic, so this is the full set for Graph Theory; try the ones that match this subtopic. Open all 24 on the topic page.