Tutte's Theorem and Matching in General Graphs

While Hall's theorem characterizes matchings in bipartite graphs, Tutte's theorem provides the analogous characterization for general graphs. The key obstruction to a perfect matching is the existence of odd components.

Tutte's Condition

Definition6.6Tutte's Theorem

A graph $G$ has a perfect matching if and only if for every $S \subseteq V(G)$ : $o(G - S) \leq |S|$ where $o(H)$ denotes the number of odd components (components with an odd number of vertices) of $H$ . Taking $S = \emptyset$ : $|V|$ must be even (necessary condition).

ExampleApplying Tutte's Condition

For $K_4$ : removing any vertex $v$ gives $K_3$ (1 odd component), and $|S| = 1 \geq 1$ . Removing two vertices gives at most 2 components, with at most 1 odd. Tutte's condition holds; indeed $K_4$ has perfect matchings. For the Petersen graph: every vertex removal gives a connected graph on 9 vertices (odd), so $o(G-v) = 1 \leq 1$ . One checks Tutte's condition holds for all $S$ ; the Petersen graph has perfect matchings.

Gallai-Edmonds Decomposition

Definition6.7Gallai-Edmonds Structure Theorem

Every graph $G$ admits a Gallai-Edmonds decomposition $V = D \cup A \cup C$ where:

$D$ = set of vertices not saturated by at least one maximum matching
$A$ = $N(D)$ (neighbors of $D$ outside $D$ )
$C$ = $V \setminus (D \cup A)$

Properties: (1) each component of $G[D]$ is factor-critical (removing any vertex leaves a graph with a perfect matching); (2) $G[C]$ has a perfect matching; (3) every maximum matching matches $A$ into distinct odd components of $G[D]$ ; (4) $\nu(G) = |V| - \max_S(o(G-S) - |S|) / 2$ (Berge formula).

RemarkFactor-Critical Graphs

A graph $H$ is factor-critical if $H - v$ has a perfect matching for every $v \in V(H)$ . Factor-critical graphs are the "building blocks" of the matching theory: they are the obstructions that create odd components. Every 2-edge-connected factor-critical graph is also brick (3-connected with no non-trivial tight cuts), and bricks are the primitive structures in matching decomposition theory.

Weighted Matching

Definition6.8Weighted Matching and the Hungarian Algorithm

In weighted bipartite matching, each edge $e$ has weight $w(e)$ , and we seek a perfect matching of minimum total weight. The Hungarian algorithm solves this in $O(n^3)$ time using dual variables (vertex potentials) $u_i, v_j$ satisfying $u_i + v_j \leq w(ij)$ . By LP duality, the minimum weight matching equals $\max(\sum u_i + \sum v_j)$ . For general graphs, Edmonds' weighted blossom algorithm solves the minimum weight perfect matching in polynomial time.