4. Matching

Maximal (Inklusionsmaximal): no matching with larger cardinality that contains the same edges Maximum (Kardinalitätsmaximal): no matching with larger cardinality

Perfect matching: covers all vertices

Prerequisite: Berge Theorem

Berge Theorem

matching non-maximal $⟺$ has augmenting path.

$⟹$: $⟸$: Flip it. Matching size increases by 1, so it cannot be maximal.

---

Greedy Algorithm

• Go through all edges. If edge is not yet in matching: add
• $|M_{\text{greedy}}|\le 2\cdot |M_{\text{opt}}|$

Augmented Paths Algorithm

Augmented Path: A path that starts and ends at unmatched nodes, alternating between unmatched and matched edges. “Flipping” the edges along this path increases the total matching by 1.

Before flip: A ---free---- B ==matched== C ---free---- D
After flip:  A ==matched== B ---free---- C ==matched== D

How it works:

1. Start with an empty matching (no pairs)
2. For each unmatched left node: Try to find an augmenting path using DFS. If found → flip the path, gaining one more match
3. Repeat until no augmenting path can be found
4. The current matching is now maximum

Correctness:

Runtime:

Hopcroft and Karp Algorithm

---

Key Theorems

Frobenius Theorem (not in lecture)

Every $k$-regular (all vertices degree $k$) bipartite graph contains a perfect matching.

Hall’s Theorem, Marriage Theorem

Theorem

For a bipartite graph $G=(A\uplus B,E)$, there exists a matching $M$ of cardinality $|M|=|A|$ if and only if

$$|N(X)|\ge |X|\text{for all }X\subseteq A$$

where $N(X)$ are all neighbors to any node in the set $X$

Intuition: suppose $A$ is a set of women, $B$ a set of men, and an edge means a pair would be willing to marry. Hall’s condition says everyone in $A$ can be married off simultaneously $⟺$ every group of women collectively likes enough men — no subset is “too popular for too few.”

$⟹$: if we have a matching, then the neighborhood of every subset must contain at least as many nodes as the subset. $⟸$:

Tricks

In $2^k$-regular graphs, one can find a perfect matching in $\mathcal{O}(|E|)$ by finding an Eulerian cycle and then deleting every second edge.