Introduction to Graph Theory/Matchings and Factors

Chapter 3: Matchings and Factors

Overview

Chapter 3 of Introduction to Graph Theory (by Douglas B. West) develops the theory of matchings -- sets of independent edges in graphs -- and the related optimization problems of covering vertices and edges. The chapter progresses from foundational results in bipartite graphs to efficient algorithms, and then to the more complex setting of general (non-bipartite) graphs. Throughout, the emphasis is on min-max duality: pairing a maximization problem with a minimization problem so that optimal solutions certify each other.

The chapter is organized into three sections:

• 3.1 Matchings and Covers -- Foundational theory including Hall's Theorem, König–Egerváry Theorem, independent sets, edge covers, and dominating sets.
• 3.2 Algorithms and Applications -- The Augmenting Path Algorithm for bipartite matching, weighted bipartite matching, and the Hungarian Algorithm.
• 3.3 Matchings in General Graphs -- Tutte's 1-Factor Theorem, the Berge–Tutte Formula, Edmonds' Blossom Algorithm, and factors of graphs.

3.1 Matchings and Covers

Basic Definitions

• Matching (Def. 3.1.1): A set of non-loop edges with no shared endpoints. Vertices incident to matching edges are saturated; others are unsaturated. A perfect matching saturates every vertex.
• Perfect matchings in $ K_{n,n} $ (Ex. 3.1.2): The number of perfect matchings in $ K_{n,n} $ corresponds to the number of permutations, i.e., $ n! $. Each can be represented as a permutation matrix.
• Perfect matchings in $ K_{2n} $ (Ex. 3.1.3): The number of perfect matchings in the complete graph $ K_{2n} $ is $ f_n = (2n-1)(2n-3) \cdots 1 = \frac{(2n)!}{2^n \cdot n!} $.

Maximum Matchings

• Maximal vs. Maximum (Def. 3.1.4): A maximal matching cannot be enlarged by adding an edge; a maximum matching has the largest possible size. Every maximum matching is maximal, but not conversely. The smallest graph illustrating the distinction is $ P_4 $.
• M-alternating path (Def. 3.1.6): A path that alternates between edges in $ M $ and edges not in $ M $. An M-augmenting path is an M-alternating path whose endpoints are both unsaturated.
• Symmetric difference (Def. 3.1.7): For matchings $ M $ and $ M' $, the symmetric difference $ M \triangle M' $ consists of edges in exactly one of the two matchings.
• Lemma 3.1.9: Every component of the symmetric difference of two matchings is a path or an even cycle.
• Berge's Theorem (Thm. 3.1.10, 1957): A matching $ M $ is maximum if and only if there is no M-augmenting path. This characterization is the foundation of all augmentation-based matching algorithms.

Hall's Matching Condition

• Hall's Theorem (Thm. 3.1.11, 1935): An X,Y-bigraph $ G $ has a matching that saturates $ X $ if and only if $ |N(S)| \geq |S| $ for all $ S \subseteq X $. This necessary and sufficient condition is known as Hall's Condition.
• The proof works by contrapositive: if a maximum matching $ M $ fails to saturate $ X $, one constructs a set $ S $ violating Hall's Condition by tracing M-alternating paths from an unsaturated vertex.
• Marriage Theorem: When $ |X| = |Y| $, Hall's Theorem becomes the Marriage Theorem (Frobenius, 1917): if every man is compatible with $ k $ women and every woman is compatible with $ k $ men, a perfect matching must exist.
• Corollary 3.1.13: Every k-regular bipartite graph ($ k > 0 $) has a perfect matching. The proof verifies Hall's Condition using a counting argument on edges.

Min-Max Theorems

• Vertex cover (Def. 3.1.14): A set $ Q $ of vertices such that every edge has at least one endpoint in $ Q $.
• König–Egerváry Theorem (Thm. 3.1.16, König 1931, Egerváry 1931): In a bipartite graph, the maximum size of a matching equals the minimum size of a vertex cover. This is the prototypical min-max theorem.
• Min-max relation (Remark 3.1.17): A theorem equating the optimum of a maximization problem with the optimum of a minimization problem over a class of instances. The König–Egerváry Theorem is such a relation for vertex covering and matching in bipartite graphs.
• Dual pair concept: A maximization problem $ \mathcal{M} $ and minimization problem $ \mathcal{N} $ are dual when for every candidate solution $ M $ to $ \mathcal{M} $ and $ N $ to $ \mathcal{N} $, the value of $ M $ is at most the value of $ N $. Equal values certify mutual optimality.

Independent Sets and Covers

• Independence number $ \alpha(G) $: The maximum size of an independent set of vertices.
• Edge cover (Def. 3.1.19): A set $ L $ of edges such that every vertex is incident to some edge of $ L $. Only graphs without isolated vertices have edge covers.
• Notation (Def. 3.1.20):
  • $ \alpha(G) $ = maximum independent set size
  • $ \alpha'(G) $ = maximum matching size
  • $ \beta(G) $ = minimum vertex cover size
  • $ \beta'(G) $ = minimum edge cover size
• Lemma 3.1.21: $ S $ is an independent set if and only if its complement $ V(G) - S $ is a vertex cover. Hence $ \alpha(G) + \beta(G) = n(G) $.
• Gallai's Theorem (Thm. 3.1.22, 1959): For any graph without isolated vertices, $ \alpha'(G) + \beta'(G) = n(G) $. The proof constructs an edge cover of size $ n(G) - |M| $ from a maximum matching $ M $, and a matching of size $ n(G) - |L| $ from a minimum edge cover $ L $.
• Corollary 3.1.24 (König, 1916): For a bipartite graph with no isolated vertices, $ \alpha(G) = \beta'(G) $. This follows from combining Gallai's Theorem with the König–Egerváry Theorem.

Dominating Sets (Optional)

• Dominating set (Def. 3.1.26): A set $ S $ of vertices such that every vertex not in $ S $ has a neighbor in $ S $. The domination number $ \gamma(G) $ is the minimum size of a dominating set.
• Closed neighborhood (Def. 3.1.29): $ N[v] = N(v) \cup \{v\} $, the set of vertices dominated by $ v $.
• Theorem 3.1.30 (Arnautov 1974, Payan 1975): Every n-vertex graph with minimum degree $ k $ has a dominating set of size at most $ \frac{n(1 + \ln(k+1))}{k+1} $. The proof uses a greedy algorithm.
• Connected, independent, and total dominating sets (Def. 3.1.32): Variations requiring the induced subgraph on $ S $ to be connected, independent, or have no isolated vertices, respectively.
• Lemma 3.1.33: A set of vertices is an independent dominating set if and only if it is a maximal independent set.
• Theorem 3.1.34 (Bollobás–Cockayne, 1979): Every claw-free graph has an independent dominating set of size $ \gamma(G) $.

3.2 Algorithms and Applications

Maximum Bipartite Matching

• Augmenting Path Algorithm (Alg. 3.2.1): Given an X,Y-bigraph $ G $, a matching $ M $, and the set $ U $ of M-unsaturated vertices in $ X $, the algorithm explores M-alternating paths from $ U $. It builds sets $ S \subseteq X $ (vertices reached) and $ T \subseteq Y $ (vertices reached). If an unsaturated vertex $ y \in Y $ is found, an augmenting path is reported. Otherwise, $ T \cup (X - S) $ is reported as a minimum vertex cover, and $ M $ as a maximum matching.
• Theorem 3.2.2: Repeatedly applying the Augmenting Path Algorithm produces both a maximum matching and a minimum vertex cover of equal size, providing an algorithmic proof of the König–Egerváry Theorem.
• Running time (Def. 3.2.3, Remark 3.2.4): The algorithm runs in $ O(nm) $ time for a bipartite graph with $ n $ vertices and $ m $ edges, since each of the at most $ n/2 $ augmentation phases explores each edge at most once. A faster algorithm achieves $ O(\sqrt{n} \cdot m) $ (referenced as Theorem 3.2.22).

Weighted Bipartite Matching

• Assignment Problem (Def. 3.2.6): Given an $ n \times n $ matrix of weights, find a transversal (one entry per row and column) with maximum total weight. This is equivalent to finding a maximum weight perfect matching in $ K_{n,n} $.
• Weighted cover (Def. 3.2.6): Labels $ u_1, \ldots, u_n $ and $ v_1, \ldots, v_n $ such that $ u_i + v_j \geq w_{i,j} $ for all $ i, j $. The cost $ c(u,v) = \sum u_i + \sum v_j $. The dual problem is finding a minimum weighted cover.
• Lemma 3.2.7: A perfect matching $ M $ and cover $ (u,v) $ are both optimal if and only if $ c(u,v) = w(M) $, i.e., $ u_i + v_j = w_{i,j} $ for every edge $ x_i y_j \in M $. This is the complementary slackness condition.
• Equality subgraph (Def. 3.2.8): $ G_{u,v} $ is the spanning subgraph of $ K_{n,n} $ with edges $ x_i y_j $ where $ u_i + v_j = w_{i,j} $. A perfect matching in $ G_{u,v} $ is optimal.
• Hungarian Algorithm (Alg. 3.2.9, Kuhn 1955, Munkres 1957): Iteratively adjusts the cover $ (u,v) $ until the equality subgraph has a perfect matching. Initialize with $ u_i = \max_j w_{i,j} $ and $ v_j = 0 $. At each iteration, find a maximum matching in $ G_{u,v} $; if not perfect, compute $ \epsilon $ (the minimum excess on uncovered positions) and adjust labels to expand the equality subgraph.
• Excess matrix: The matrix $ c_{i,j} = u_i + v_j - w_{i,j} $ provides a computational framework. Edges of $ G_{u,v} $ correspond to zeros. A matching in $ G_{u,v} $ is a set of zeros with no two in the same row or column (partial transversal). A covering set of rows and columns covering all zeros corresponds to a vertex cover.
• Theorem 3.2.11: The Hungarian Algorithm finds a maximum weight matching and a minimum cost cover, with the two having equal total value.

Stable Matchings (Gale–Shapley Algorithm)

Section 3.2 also covers applications including:

• Stable matchings in the context of the Gale–Shapley proposal algorithm, used in problems such as the National Resident Matching Program. A stable matching has no "blocking pair" -- a pair that would both prefer each other to their current partners.

3.3 Matchings in General Graphs

The Challenge of Odd Cycles

The theory of matchings in general (non-bipartite) graphs is considerably more complex than in bipartite graphs. The key complication is the presence of odd cycles: Hall's Condition and the König–Egerváry Theorem do not hold for general graphs. New structural concepts are required.

Tutte's 1-Factor Theorem

• Odd components: A component of a graph is odd if it has an odd number of vertices. The number of odd components of $ G - S $ is denoted $ o(G - S) $.
• Tutte's Theorem (1947): A graph $ G $ has a perfect matching (1-factor) if and only if for every subset $ S $ of $ V(G) $, the number of odd components $ o(G - S) \leq |S| $. This is the fundamental necessary and sufficient condition for perfect matchings in general graphs.
• Necessity: If $ G $ has a perfect matching $ M $, each odd component of $ G - S $ must send at least one matching edge to $ S $, so $ o(G - S) \leq |S| $.

The Berge–Tutte Formula

• Berge–Tutte Formula: The maximum size of a matching in a graph $ G $ equals:

$ \min_{S \subseteq V(G)} \frac{1}{2}\left(n(G) - o(G - S) + |S|\right) $

This generalizes Tutte's Theorem (which is the special case where the maximum matching has size $ n/2 $) and serves as the general graph analogue of the König–Egerváry Theorem.

• The deficiency of a set $ S $, defined as $ o(G - S) - |S| $, measures how far the graph is from having a perfect matching.

Edmonds' Blossom Algorithm

• Blossoms: An odd cycle in the context of an alternating tree is called a blossom. When the augmenting path search in a general graph encounters an odd cycle, it cannot simply ignore it (as in bipartite graphs where odd cycles do not exist).
• Edmonds' Algorithm (1965): The key insight is blossom shrinking: when an odd cycle (blossom) is discovered during the search, it is contracted to a single vertex. Augmenting paths in the contracted graph correspond to augmenting paths in the original graph. After finding an augmenting path (or certifying that none exists), the blossoms are expanded.
• The algorithm runs in polynomial time, specifically $ O(n^3) $ with careful implementation, providing an efficient algorithm for maximum matching in general graphs.

Factors of Graphs

• k-factor: A k-regular spanning subgraph. A 1-factor is a perfect matching; a 2-factor is a spanning union of disjoint cycles.
• Petersen's Theorem (1891): Every bridgeless 3-regular graph has a perfect matching (1-factor). This classical result demonstrates that high connectivity combined with regularity guarantees matchings.
• f-factor: A more general concept where each vertex $ v $ must have degree $ f(v) $ in the spanning subgraph, for a prescribed function $ f $. Tutte provided a characterization of when a graph has an f-factor.

Key Themes and Significance

1. Min-max duality: The chapter repeatedly demonstrates that optimal solutions to dual problems certify each other. This paradigm (maximum matching = minimum vertex cover in bipartite graphs; Tutte's condition for general graphs) is central to combinatorial optimization.
2. Algorithmic constructiveness: Every existence theorem is accompanied by an efficient algorithm. The Augmenting Path Algorithm constructively finds maximum matchings and minimum covers; the Hungarian Algorithm solves weighted matching; Edmonds' Blossom Algorithm handles general graphs.
3. Bipartite vs. general: The clean theory of bipartite matching (Hall, König–Egerváry) breaks down for general graphs due to odd cycles. The resolution -- Tutte's Theorem and blossom shrinking -- represents some of the deepest results in combinatorial optimization.
4. Connections to linear programming: The duality between matchings and covers corresponds to LP duality. The König–Egerváry Theorem is equivalent to the total unimodularity of the incidence matrix of bipartite graphs, and the Hungarian Algorithm is essentially the dual simplex method applied to the assignment problem.