Exercises — Matching
Chapter 12 · Fully solved exercises on bipartite matching, augmenting paths, and König’s theorem
Exercise 1: Find the Maximum Matching
Problem. Consider the bipartite graph with \(L = \{u_1, u_2, u_3\}\) and \(R = \{v_1, v_2, v_3, v_4\}\), edges: \(u_1\)–\(v_1\), \(u_1\)–\(v_2\), \(u_2\)–\(v_2\), \(u_2\)–\(v_3\), \(u_3\)–\(v_3\), \(u_3\)–\(v_4\).
Starting from the matching \(M = \{u_1\text{-}v_1,\ u_2\text{-}v_3\}\), find the maximum matching using augmenting paths.
Solution
\(|M| = 2\). Exposed nodes: \(u_3\) on the left; \(v_2, v_4\) on the right.
We search for an augmenting path starting from \(u_3\):
- \(u_3\) can reach \(v_3\) (not in \(M\) — but \(v_3\) is matched to \(u_2\)) or \(v_4\) (not in \(M\), exposed).
- \(u_3 \to v_4\): \(v_4\) is exposed. Augmenting path found: \(u_3\)–\(v_4\) (length 1).
Augment \(M\) along this path:
\[M' = M \cup \{u_3\text{-}v_4\} = \{u_1\text{-}v_1,\ u_2\text{-}v_3,\ u_3\text{-}v_4\}, \quad |M'| = 3.\]
Is \(M'\) maximum? All three \(L\)-nodes are matched. Since \(|M| \le |L| = 3\) always, we have reached the upper bound. \(M'\) is a maximum matching.
Exercise 2: Augmenting Path with Alternation
Problem. Bipartite graph: \(L = \{p, q, r, s\}\), \(R = \{w, x, y, z\}\). Edges: \(p\)–\(w\), \(p\)–\(x\), \(q\)–\(x\), \(q\)–\(y\), \(r\)–\(y\), \(r\)–\(z\), \(s\)–\(z\), \(s\)–\(w\). Starting matching \(M = \{p\text{-}w,\ q\text{-}y,\ r\text{-}z\}\). Find an augmenting path and improve the matching.
Solution
Exposed nodes: \(s\) on the left (unmatched); \(x\) on the right (unmatched).
BFS from \(s\) along an alternating path (non-matching, then matching, then non-matching, …):
| Step | Node | Via edge (type) | Note |
|---|---|---|---|
| 1 | \(s\) | — | start |
| 2 | \(w\) | \(s\)–\(w\) (non-M) | \(w\) is matched to \(p\) |
| 3 | \(p\) | \(w\)–\(p\) (in \(M\), reverse) | \(p\) can reach \(x\) |
| 4 | \(x\) | \(p\)–\(x\) (non-M) | \(x\) is exposed → path found! |
Augmenting path: \(s\)–\(w\)–\(p\)–\(x\).
Alternation check: non-M, in-M, non-M. ✓
Augment by symmetric difference:
\[M' = M \oplus \{s\text{-}w,\ w\text{-}p,\ p\text{-}x\} = \{p\text{-}x,\ q\text{-}y,\ r\text{-}z,\ s\text{-}w\}, \quad |M'| = 4.\]
This is a perfect matching (all four \(L\)-nodes and all four \(R\)-nodes are matched).
Exercise 3: König’s Theorem
Problem. For the bipartite graph of Exercise 2, after finding the maximum matching \(M' = \{p\text{-}x,\ q\text{-}y,\ r\text{-}z,\ s\text{-}w\}\):
- What is the maximum matching size?
- Find a minimum vertex cover.
- Verify König’s theorem: \(|\text{max matching}| = |\text{min vertex cover}|\).
Solution
(a) \(M'\) is a perfect matching: \(|M'| = 4\).
(b) A vertex cover is a set \(C\) of vertices such that every edge has at least one endpoint in \(C\).
Since the matching has size 4, any vertex cover needs at least 4 vertices (each matching edge must be covered). The entire right side \(R = \{w, x, y, z\}\) covers every edge (each edge \(\ell\)–\(r\) has \(r \in R\)). Similarly \(L = \{p, q, r, s\}\) works.
\[\text{Minimum vertex cover: } C = \{w, x, y, z\}, \quad |C| = 4.\]
Every edge has its right endpoint in \(C\). ✓
(c)
| Quantity | Value |
|---|---|
| Max matching \(|M'|\) | 4 |
| Min vertex cover \(|C|\) | 4 |
| König’s theorem | \(4 = 4\) ✓ |
König’s theorem (bipartite graphs only): in every bipartite graph, the size of a maximum matching equals the size of a minimum vertex cover.
Exercise 4: Hall’s Theorem
Problem. Bipartite graph: \(L = \{a, b, c\}\), \(R = \{1, 2, 3, 4\}\). Edges: \(a\)–1, \(a\)–2, \(b\)–2, \(b\)–3, \(c\)–3, \(c\)–4.
- Does a perfect matching on \(L\) exist?
- Check Hall’s condition for all subsets \(S \subseteq L\).
Solution
Hall’s theorem: a perfect matching saturating all \(L\)-nodes exists if and only if for every \(S \subseteq L\), \(|N(S)| \ge |S|\), where \(N(S)\) is the neighborhood of \(S\) in \(R\).
(b) Checking all \(2^3 - 1 = 7\) non-empty subsets:
| \(S\) | \(N(S)\) | \(|N(S)|\) | \(|S|\) | Hall? |
|---|---|---|---|---|
| \(\{a\}\) | \(\{1,2\}\) | 2 | 1 | ✓ |
| \(\{b\}\) | \(\{2,3\}\) | 2 | 1 | ✓ |
| \(\{c\}\) | \(\{3,4\}\) | 2 | 1 | ✓ |
| \(\{a,b\}\) | \(\{1,2,3\}\) | 3 | 2 | ✓ |
| \(\{a,c\}\) | \(\{1,2,3,4\}\) | 4 | 2 | ✓ |
| \(\{b,c\}\) | \(\{2,3,4\}\) | 3 | 2 | ✓ |
| \(\{a,b,c\}\) | \(\{1,2,3,4\}\) | 4 | 3 | ✓ |
Hall’s condition holds for every subset → a perfect matching on \(L\) exists.
(a) Three valid perfect matchings on \(L\): \(\{a\text{-}1,\ b\text{-}2,\ c\text{-}3\}\), \(\{a\text{-}1,\ b\text{-}3,\ c\text{-}4\}\), \(\{a\text{-}2,\ b\text{-}3,\ c\text{-}4\}\).
Exercise 5: Matching via Maximum Flow
Problem. For the bipartite graph of Exercise 1: \(L = \{u_1, u_2, u_3\}\), \(R = \{v_1, v_2, v_3, v_4\}\), edges: \(u_1\)–\(v_1\), \(u_1\)–\(v_2\), \(u_2\)–\(v_2\), \(u_2\)–\(v_3\), \(u_3\)–\(v_3\), \(u_3\)–\(v_4\).
Formulate as a max-flow problem and find the maximum matching.
Solution
Reduction to max flow. Build the directed network \(G'\):
- Add a source \(s\) with arcs \(s \to u_i\) of capacity 1 for each \(u_i \in L\).
- Add a sink \(t\) with arcs \(v_j \to t\) of capacity 1 for each \(v_j \in R\).
- Orient each bipartite edge \(u_i\)–\(v_j\) as \(u_i \to v_j\), capacity 1.
Ford-Fulkerson (augmenting paths in residual graph):
| Augmentation | Path | Flow added |
|---|---|---|
| 1 | \(s \to u_1 \to v_1 \to t\) | +1 |
| 2 | \(s \to u_2 \to v_2 \to t\) | +1 |
| 3 | \(s \to u_3 \to v_3 \to t\) | +1 |
| — | No more augmenting paths | — |
Max flow = 3. All arcs \(s \to u_i\) are saturated; no further path exists.
Reading the matching: set \(M = \{(u_i, v_j) : \text{flow on } u_i \to v_j = 1\}\).
\[M = \{u_1\text{-}v_1,\ u_2\text{-}v_2,\ u_3\text{-}v_3\}, \quad |M| = 3 = \text{max flow}.\]
Note: \(v_4\) is unused (no flow through it). An alternative max matching of the same size \(\{u_1\text{-}v_1, u_2\text{-}v_3, u_3\text{-}v_4\}\) is equally valid.
Max flow = max matching: 3 = 3 ✓