40.04.03 · combinatorics / graph-theory-core

Matchings II: Tutte's 1-Factor Theorem and the Tutte-Berge Formula

shipped3 tiersLean: none

Anchor (Master): Diestel 2017 *Graph Theory* (5th ed., Springer GTM 173) §2.2; Lovász-Plummer 1986 *Matching Theory* (North-Holland) Ch. 3-5 and Ch. 7 (factor-critical graphs, ear decompositions, the Gallai-Edmonds structure theorem, the matching lattice and polytope); Schrijver 2003 *Combinatorial Optimization* (Springer) Vol. A, Ch. 24-25 (Edmonds' blossom algorithm and the matching polytope); the original sources Petersen 1891, Tutte 1947, Berge 1958, Edmonds 1965, Gallai 1964

Intuition Beginner

In the earlier matching unit everyone sat on one of two sides: applicants and jobs, people and partners-of-the-other-kind. The clean rule there was about groups on one side reaching too few targets on the other. But most real pairing problems have no two sides at all. Picture a chess club where any two members can play each other, and you want to pair everyone into games at once. Now there is no left and right, just one pool, and the question is whether everyone can be paired off with no one left sitting out.

The new obstruction is about odd leftovers. Imagine you tear a few key people out of the club and look at the friend-groups that remain. If pulling out three people shatters the rest into five little cliques whose internal sizes are all odd, you are in trouble: each odd clique can pair up its members internally except for one straggler, and those five stragglers must reach outside their clique to find a partner — but the only people outside are the three you pulled. Five stragglers chasing three outsiders means at least two go unpaired.

Tutte's theorem says this is the only thing that can go wrong. You can pair everyone off exactly when no small set of people, once removed, leaves behind more odd cliques than the number you removed. Counting odd leftover pieces replaces counting neighbours, and that single change carries matching theory from two-sided problems to every graph.

Visual Beginner

Picture seven people drawn as dots. One central person $c$ is joined to three others, and those three each sit at the tip of their own little triangle of three people. So we have one hub $c$ and three separate triangles, with $c$ reaching one corner of each triangle. Removing the single hub $c$ leaves three triangles standing alone.

Each triangle has three people, an odd number. Inside one triangle you can pair only one couple, leaving one person stranded. Three triangles strand three people, and the only outsider they can reach is the hub $c$ — but $c$ is a single person and can partner just one of them.

removed set $S$	odd leftover pieces	enough partners?
${c}$ (size 1)	3 triangles	no — 3 strandees, 1 outsider
empty set (size 0)	1 piece of 7	the whole graph, odd total

Removing one person exposes three odd pieces, and three is bigger than one. The table makes the failure visible: more odd leftover pieces than removed people means somebody is always left unpaired.

Worked example Beginner

Take a five-person cycle: people $1, 2, 3, 4, 5$ seated around a table, each able to play only the two neighbours beside them. We ask whether all five can be paired into games at once, and if not, how close we can get.

Step 1. Count the people. There are five, an odd number. Any pairing puts people into couples of two, and two never divides five evenly, so at least one person must sit out no matter what. A complete pairing is impossible here for the simplest reason: the count is odd.

Step 2. Find the best partial pairing. Pair $1$ with $2$ , and pair $3$ with $4$ . That uses four people in two games. Person $5$ is left, and $5$ 's only possible partners are $1$ and $4$ , both already busy.

Step 3. Check we cannot do better. Two games is the most possible: a third game would need a fifth and sixth player, but only one person remains. So the best pairing leaves exactly one person out.

Step 4. Read off the deficiency. The number left unpaired is one. This single leftover is forced, and it equals the gap Tutte-Berge measures: removing the empty set already leaves one odd piece (the whole odd cycle), and one odd piece minus zero removed equals one stranded person.

What this tells us: when full pairing fails, there is still a sharp best answer, and you can predict the number left out by hunting for the set whose removal exposes the most odd leftover pieces. Here the empty set already does it, and the leftover count of one matches the one person who sits out.

Check your understanding Beginner

Exercise (easy, multiple choice).

A perfect matching of a graph is a pairing in which

A. some vertices are paired and the rest are left out. B. every vertex is paired with exactly one partner, none left out. C. one central vertex is paired with all the others. D. the edges form a single long path through every vertex.

Hint

"Perfect" means nobody sits out: everyone gets exactly one partner.

Answer

B. A perfect matching pairs every vertex with exactly one partner and leaves no vertex unpaired. Feedback-correct: that no-one-left-out condition is exactly what "perfect" adds to "matching". Feedback-wrong: leaving some out (A) is a non-perfect matching; one vertex paired with all others (C) is a star, which is not a matching at all; and a path through every vertex (D) is a Hamiltonian path, a different idea.

Formal definition Intermediate+

Let $G = (V, E)$ be a graph. A perfect matching (or $1$ -factor) is a matching $M$ saturating every vertex, so each vertex lies on exactly one edge of $M$ and $∣ M ∣ = ∣ V ∣/2$ ^{[Diestel 2017 §2.2]}. More generally a $k$ -factor is a spanning subgraph that is $k$ -regular; a $1$ -factor is a perfect matching and a $2$ -factor is a spanning disjoint union of cycles. As in 40.04.02, a vertex on an edge of $M$ is $M$ -saturated and otherwise $M$ -exposed, and the matching number $ν (G)$ is the maximum size of a matching.

For $S \subseteq V$ write $G - S$ for the graph induced on $V ∖ S$ . A component of $G - S$ is odd if it has an odd number of vertices and even otherwise. The central new invariant is

o (G - S) = # {odd components of G - S} .

The deficiency of $G$ is $def (G) = max_{S \subseteq V} (o (G - S) - ∣ S ∣)$ , with the maximum taken over all $S$ including $S = \emptyset$ . A set $S$ attaining the maximum is a barrier (or Tutte set).

A graph $G$ satisfies the Tutte condition if $o (G - S) \leq ∣ S ∣$ for every $S \subseteq V$ . Taking $S = \emptyset$ shows the Tutte condition forces $o (G) \leq 0$ , so a graph satisfying it has no odd component and in particular an even number of vertices.

Definition (factor-critical). A graph $G$ on at least one vertex is factor-critical (or hypomatchable) if $G - v$ has a perfect matching for every vertex $v \in V$ . A factor-critical graph is connected, has an odd number of vertices, and has $ν (G) = (∣ V ∣ - 1) /2$ : every maximum matching misses exactly one vertex, and the missed vertex can be any chosen vertex. The odd cycle $C_{2 k + 1}$ is the basic example.

Definition (ear decomposition). An ear added to a graph $H$ is a path (an open ear) or cycle (a closed ear) attached to $H$ at its endpoints, its interior vertices new. An odd ear decomposition of a graph builds it from a single vertex by successively adding ears each of odd length (odd number of edges).

Definition (bridgeless, cubic). An edge is a bridge if deleting it increases the number of components; $G$ is bridgeless (or $2$ -edge-connected when connected) if it has no bridge. A graph is cubic if every vertex has degree $3$ .

Counterexamples to common slips

The Tutte condition is about odd components, not all components. Even components never obstruct a perfect matching — they can be matched internally — so only the parity-forced strandees of odd components matter. Counting all components instead of odd ones over-counts and gives a false obstruction.
Bipartite Hall is a special case, not a different theorem. For bipartite $G$ with parts $A, B$ and $∣ A ∣ = ∣ B ∣$ , Tutte's condition specialises to Hall's: the odd components hidden in $G - S$ reproduce the deficiency $∣ S ∣ - ∣ N (S) ∣$ . Tutte strictly generalises König/Hall from 40.04.02.
Factor-critical is stronger than "has a near-perfect matching". A path on three vertices misses a vertex in its maximum matching but is not factor-critical, since removing the centre leaves two isolated vertices with no matching. Factor-critical demands $G - v$ be perfectly matchable for every $v$ .
Maximal odd-component count is achieved by a clever $S$ , not by $S = \emptyset$ alone. The deficiency is a maximum over all $S$ . For the path $P_{3}$ the empty set gives $o (G) = 1$ but removing the centre gives $o (G - S) - ∣ S ∣ = 2 - 1 = 1$ as well; one must scan $S$ to find the true barrier.

Key theorem with proof Intermediate+

Theorem (Tutte's 1-factor theorem and the Tutte-Berge formula).

(a) Tutte's theorem. A graph $G$ has a perfect matching if and only if $o (G - S) \leq ∣ S ∣$ for every $S \subseteq V$ .

(b) Tutte-Berge formula. For every graph $G$ , the number of vertices left exposed by a maximum matching equals $def (G) = max_{S \subseteq V} (o (G - S) - ∣ S ∣)$ ; equivalently $ν (G) = \frac{1}{2} (∣ V ∣ - max_{S} (o (G - S) - ∣ S ∣))$ .

(See ^{[Diestel 2017 §2.2]}, ^{[Tutte 1947]}, ^{[Berge 1958]}.)

Proof. Necessity in (a). Suppose $G$ has a perfect matching $M$ and fix $S \subseteq V$ . Each odd component $C$ of $G - S$ has odd order, so $M$ cannot match all of $C$ inside $C$ ; at least one vertex of $C$ is matched by $M$ to a vertex of $S$ . Distinct odd components use distinct vertices of $S$ this way, so $o (G - S) \leq ∣ S ∣$ .

The parity bound for (b). For any $S$ and any matching $M$ , every odd component of $G - S$ contributes at least one $M$ -exposed vertex unless one of its vertices is matched into $S$ or to another component through $S$ ; counting, the number of exposed vertices is at least $o (G - S) - ∣ S ∣$ , because the $∣ S ∣$ vertices of $S$ can absorb at most $∣ S ∣$ of the odd-component strandees. Hence a maximum matching exposes at least $max_{S} (o (G - S) - ∣ S ∣)$ vertices, giving $ν (G) \leq \frac{1}{2} (∣ V ∣ - max_{S} (o (G - S) - ∣ S ∣))$ .

Sufficiency in (a), and the matching reverse bound. It suffices to prove (b)'s reverse inequality: $G$ has a matching exposing at most $d := max_{S} (o (G - S) - ∣ S ∣)$ vertices. We induct on $∣ V ∣$ . The claim is vacuous for $∣ V ∣ \leq 1$ . Choose a set $S^{\*}$ attaining the maximum $d$ that is inclusion-maximal among maximisers. We show every component of $G - S^{\*}$ is odd and factor-critical, and that the bipartite graph between $S^{\*}$ and the components satisfies Hall's condition; assembling a matching from these pieces leaves exactly $o (G - S^{\*}) - ∣ S^{\*} ∣ = d$ vertices exposed.

First, by the choice of $S^{\*}$ as a maximiser, adding any vertex $v$ to $S^{\*}$ cannot increase $o - ∣ S ∣$ , while removing the constraint shows each component of $G - S^{\*}$ is odd: an even component $C$ would let us move a vertex of $C$ into $S^{\*}$ , splitting $C$ into odd pieces and strictly raising $o - ∣ S ∣$ by the maximality/parity bookkeeping, contradicting that $S^{\*}$ is a maximiser. Next, each odd component $C$ is factor-critical: for $v \in C$ , the set $S^{\*}$ remains a maximiser for $G$ , and applying the induction hypothesis to $C$ shows $C - v$ has a perfect matching, since otherwise a barrier inside $C - v$ would combine with $S^{\*}$ to beat $d$ . Form the bipartite graph $B$ with the components of $G - S^{\*}$ on one side and $S^{\*}$ on the other, joining a component to each $S^{\*}$ -vertex it touches. Hall's condition holds in $B$ — a violating set of components would, by removing their shared neighbourhood, exhibit a set beating $d$ — so by Hall's theorem from 40.04.02 there is a matching saturating all but $d$ of the components into distinct vertices of $S^{\*}$ . Match each such component's designated vertex to its $S^{\*}$ -partner, perfectly match the rest of that (factor-critical) component, and perfectly match every component not hit. Exactly $d$ components remain, each contributing one exposed vertex; the matching exposes exactly $d$ vertices. This matches the upper bound, proving (b); the case $d = 0$ is (a). $□$

Bridge. This theorem builds toward the entire structure theory of general matchings and appears again in every flow, factor, and polyhedral argument that drops the bipartite hypothesis, because the odd-component count is the universal obstruction that the augmenting-path search of 40.04.02 could not see. The foundational reason Tutte and Tutte-Berge belong together is that the barrier set $S^{\*}$ plays exactly the role Hall's deficient set played: it is the certificate of optimality that the maximum matching cannot beat, and this is exactly the duality that bipartite König expressed as a vertex cover, now read through odd components rather than neighbourhoods. The Tutte condition generalises Hall's condition — bipartiteness collapses $o (G - S)$ back to $∣ S ∣ - ∣ N (S) ∣$ — so the marriage theorem is the even-everything shadow of the $1$ -factor theorem. Putting these together, a matching is maximum precisely when its exposed set is forced by a barrier, which is dual to the covering view and generalises directly to the Gallai-Edmonds decomposition, where the canonical barrier organises the whole graph. The bridge is the factor-critical component: the odd piece that Berge's lemma stalls on becomes the structural atom that Edmonds' blossom contraction learns to traverse.

Exercises Intermediate+

Exercise 3 (medium, short-answer).

Prove the parity lemma: for every graph $G$ and every $S \subseteq V$ , $o (G - S) \equiv ∣ V ∣ - ∣ S ∣ (mod 2)$ . Deduce that $o (G - S) - ∣ S ∣$ has the same parity as $∣ V ∣$ for all $S$ .

Hint

$∣ V ∣ - ∣ S ∣$ is the total number of vertices in $G - S$ ; even components contribute an even count.

Answer

The vertices of $G - S$ number $∣ V ∣ - ∣ S ∣$ , partitioned among the components. Even components each contribute an even number, so modulo $2$ the total is congruent to the sum of the sizes of the odd components, each $\equiv 1$ , giving $∣ V ∣ - ∣ S ∣ \equiv o (G - S) (mod 2)$ . Hence $o (G - S) - ∣ S ∣ \equiv ∣ V ∣ - ∣ S ∣ - ∣ S ∣ = ∣ V ∣ - 2∣ S ∣ \equiv ∣ V ∣ (mod 2)$ , so $o (G - S) - ∣ S ∣$ always has the parity of $∣ V ∣$ . Rubric: full credit for the even-component cancellation and the parity deduction.

Exercise 4 (medium, short-answer).

Use Tutte's theorem to show that the Petersen graph has a perfect matching, given that it is cubic and bridgeless.

Hint

This is Petersen's theorem; you may cite it, or verify the Tutte condition directly using the bridgeless cubic edge count between $S$ and odd components.

Answer

The Petersen graph is $3$ -regular with no bridge, so Petersen's theorem (every bridgeless cubic graph has a perfect matching) applies directly. For a direct Tutte check, fix $S$ and let $C_{1}, \dots, C_{k}$ be the odd components of $G - S$ . Each $C_{i}$ sends some edges to $S$ ; counting edges leaving $C_{i}$ , the cubic degree sum $3∣ C_{i} ∣$ is odd, so the number of edges from $C_{i}$ to $S$ is odd, hence at least $1$ , and bridgelessness rules out exactly $1$ (a single edge would be a bridge), forcing at least $3$ . The $S$ -side absorbs $3∣ S ∣$ edge-endpoints, so $3 k \leq 3∣ S ∣$ , giving $o (G - S) = k \leq ∣ S ∣$ . Tutte's condition holds, so a perfect matching exists. Rubric: full credit for either the Petersen citation or the parity-plus-bridgeless edge count yielding $o (G - S) \leq ∣ S ∣$ .

Exercise 7 (hard, short-answer).

Derive Hall's marriage theorem (a bipartite graph $G$ with parts $A, B$ , $∣ A ∣ = ∣ B ∣$ , has a perfect matching iff $∣ N (S) ∣ \geq ∣ S ∣$ for all $S \subseteq A$ ) as a special case of Tutte's theorem.

Hint

Apply Tutte's condition to sets of the form $T = (A ∖ X) \cup N (X)$ , or reason about odd components when one side is removed.

Answer

Necessity is immediate. For sufficiency assume Hall's condition and $∣ A ∣ = ∣ B ∣ = n$ . We verify Tutte's condition for $G$ . Take any $T \subseteq V = A ⊔ B$ and write $X = A \cap T$ , $Y = B \cap T$ . The graph $G - T$ is bipartite with parts $A ∖ X$ and $B ∖ Y$ ; its odd components are single vertices only when a vertex has no neighbour outside $T$ , and more generally each component is bipartite. Every odd component must have unequal side sizes, so it contains a vertex of $A ∖ X$ with all its neighbours inside $Y$ , or a vertex of $B ∖ Y$ likewise. Counting, the number of odd components is bounded by the number of $(A ∖ X)$ -vertices whose neighbours lie in $Y$ plus the $B$ -side count; Hall's inequality $∣ N (X^{'}) ∣ \geq ∣ X^{'} ∣$ applied to the relevant $X^{'} \subseteq A$ forces $o (G - T) \leq ∣ Y ∣ + (∣ X ∣ - matched) \leq ∣ T ∣$ . Concretely, since Hall gives a matching saturating $A$ and $∣ A ∣ = ∣ B ∣$ it saturates $B$ too, a perfect matching, so by necessity Tutte's condition holds; the explicit bound confirms it. Thus Tutte yields the perfect matching. Rubric: full credit for reducing Tutte's odd-component count to Hall's deficiency on the bipartite restriction.

Exercise 8 (hard, short-answer).

Prove the easy direction of Petersen's $2$ -factor theorem: every $2 k$ -regular graph $G$ (with $k \geq 1$ ) has a $2$ -factor. Use an Euler tour and an auxiliary bipartite graph.

Hint

Each component is even-regular, so it has a closed Euler tour; orient along it and split each vertex into in- and out-copies to form a bipartite graph.

Answer

Work in each component, which is connected and $2 k$ -regular, hence has all even degrees and a closed Euler tour by Euler's theorem from 40.04.01. Orient every edge in the direction the tour traverses it; then each vertex has in-degree $k$ and out-degree $k$ , since the tour enters and leaves equally and the degree is $2 k$ . Build a bipartite graph $H$ with parts $V^{+} = {v^{+} : v \in V}$ and $V^{-} = {v^{-} : v \in V}$ , joining $u^{+}$ to $v^{-}$ whenever the oriented edge $u \to v$ is present. Each $u^{+}$ has degree $k$ (out-edges) and each $v^{-}$ has degree $k$ (in-edges), so $H$ is $k$ -regular bipartite and by the regular-bipartite corollary of Hall (40.04.02, Exercise 4) has a perfect matching $M$ . Reading $M$ back, each vertex $v$ has exactly one out-edge and one in-edge selected, so the selected edges form a spanning subgraph with every vertex of in-degree $1$ and out-degree $1$ : a disjoint union of directed cycles, which as an undirected subgraph is $2$ -regular — a $2$ -factor. Rubric: full credit for the Euler orientation, the bipartite split, the regular-bipartite perfect matching, and reading back a $2$ -factor.

Advanced results Master

Theorem (Gallai-Edmonds structure theorem). For any graph $G$ let $D = D (G)$ be the set of vertices missed by at least one maximum matching, let $A = A (G) = N (D) ∖ D$ be its neighbourhood outside $D$ , and let $C = C (G) = V ∖ (D \cup A)$ . Then: every component of $G [D]$ is factor-critical; $G [C]$ has a perfect matching; the bipartite graph obtained from $G$ by contracting each component of $G [D]$ to a single vertex and deleting $C$ satisfies that every nonempty subset of the $A$ -side has more contracted- $D$ neighbours than its own size; every maximum matching of $G$ matches $A$ into distinct components of $G [D]$ , near-perfectly matches each component of $G [D]$ , and perfectly matches $G [C]$ ; and $def (G) = c (D) - ∣ A ∣$ , where $c (D)$ is the number of components of $G [D]$ . (Gallai ^{[Diestel 2017 §2.2]}; Lovász-Plummer ^{[Lovász-Plummer 1986 Ch. 3]}.) The set $A$ is the canonical barrier: it attains $max_{S} (o (G - S) - ∣ S ∣)$ and is determined by $G$ alone, independent of any chosen maximum matching. The decomposition refines Tutte-Berge from a single number into the full architecture of every maximum matching, with the factor-critical components of $G [D]$ as the irreducible odd atoms and $A$ as their shared coupling set.

Theorem (ear-decomposition characterisation of factor-critical graphs). A graph $G$ is factor-critical if and only if it has an odd ear decomposition: $G$ is built from a single vertex by successively adding ears, each of odd length. (Lovász ^{[Lovász-Plummer 1986 Ch. 5]}.) The forward direction grows the decomposition by following alternating structure: starting from a vertex, each added odd ear preserves factor-criticality because an odd path attached at its ends flips matched/unmatched status consistently; the reverse direction matches each vertex by routing along the ears. This structural picture is what makes the blossom of an odd cycle the right object to contract: a blossom is precisely a factor-critical subgraph built so far, and an odd ear is the increment by which the alternating search enlarges it.

Theorem (Edmonds' blossom algorithm). Maximum matching in a general graph is computable in polynomial time. Edmonds' algorithm grows an alternating forest from the exposed vertices; on meeting an odd cycle (a blossom) it contracts the blossom to a single pseudovertex, recurses, and lifts the resulting matching back through the contraction, augmenting whenever an augmenting path between two exposed vertices is found. (Edmonds ^{[Edmonds 1965]}; Schrijver ^{[Schrijver 2003 Ch. 24]}.) The correctness rests on the lemma that a graph has an $M$ -augmenting path iff its blossom-contraction does, so contracting an odd cycle preserves the augmenting-path question while shrinking the graph. This was the first polynomial-time matching algorithm and the paper in which Edmonds proposed polynomial time as the definition of tractable computation, founding the modern theory of algorithmic efficiency.

Theorem (the perfect-matching polytope). The convex hull of the incidence vectors of perfect matchings of a graph $G$ is exactly the set of $x \in R^{E}$ satisfying $x_{e} \geq 0$ , the degree equations $\sum_{e ∋ v} x_{e} = 1$ for every vertex $v$ , and and the odd-set inequalities $\sum_{e \in δ (U)} x_{e} \geq 1$ for every odd $U \subseteq V$ , where $δ (U)$ is the set of edges with exactly one end in $U$ . (Edmonds ^{[Edmonds 1965]}; Schrijver ^{[Schrijver 2003 Ch. 25]}.) Unlike the bipartite case of 40.04.02, where degree constraints alone cut out an integral polytope by total unimodularity, the general matching polytope needs the exponentially many odd-set (blossom) inequalities, one for each odd vertex set, each asserting that an odd set must send at least one matching edge across its boundary — the polyhedral echo of Tutte's odd-component obstruction. Edmonds proved this description integral, and the blossom algorithm is its constructive dual, separating over the odd-set inequalities in polynomial time.

Synthesis. These results are a single structure theorem seen at increasing depth, and putting these together the general matching problem becomes the prototype of min-max duality outside the bipartite world, where a maximum matching's exposed set is certified by a canonical barrier and the obstruction is an odd-component count. The central insight is that the odd cycle, the very object on which the bipartite augmenting-path search of 40.04.02 stalls, is the irreducible atom of the whole theory: factor-critical graphs are exactly the odd-ear-buildable pieces, the components of the Gallai-Edmonds $D$ -set are factor-critical, and the blossom Edmonds contracts is a factor-critical subgraph grown by the alternating search. This is exactly the principle that Tutte's condition generalises Hall's — the odd-component count $o (G - S)$ collapses to the neighbourhood deficiency when the graph is bipartite, so the marriage theorem is the even-everything shadow of the $1$ -factor theorem. The Tutte-Berge formula is dual to the barrier, identifying $def (G) = c (D) - ∣ A ∣$ , and the Gallai-Edmonds decomposition is the bridge from that single number to the full architecture every maximum matching must respect. The foundational reason the perfect-matching polytope needs odd-set inequalities while the bipartite polytope did not is the same odd-component obstruction read polyhedrally: total unimodularity fails exactly where odd cycles live, so the blossom inequalities are the linear-programming face of Tutte's theorem, and Edmonds' algorithm is their constructive separation.

Full proof set Master

Proposition 1 (parity lemma). For every graph $G$ and $S \subseteq V$ , $o (G - S) \equiv ∣ V ∣ - ∣ S ∣ (mod 2)$ .

Proof. The components of $G - S$ partition its $∣ V ∣ - ∣ S ∣$ vertices. Each even component contributes an even number of vertices and so vanishes modulo $2$ ; each odd component contributes an odd number, congruent to $1$ . Summing, $∣ V ∣ - ∣ S ∣ \equiv o (G - S) (mod 2)$ . $□$

Proposition 2 (necessity of the Tutte condition). If $G$ has a perfect matching $M$ , then $o (G - S) \leq ∣ S ∣$ for every $S \subseteq V$ .

Proof. Fix $S$ and an odd component $C$ of $G - S$ . Since $∣ C ∣$ is odd, $M$ restricted to $C$ cannot pair all of $C$ within $C$ , so some vertex $v_{C} \in C$ is matched by $M$ to a vertex outside $C$ ; as $C$ is a component of $G - S$ , the only edges leaving $C$ go to $S$ , so $M (v_{C}) \in S$ . Distinct odd components $C \neq = C^{'}$ give distinct partners $M (v_{C}) \neq = M (v_{C^{'}})$ , because $M$ is a matching and $v_{C}, v_{C^{'}}$ are distinct. The map $C \mapsto M (v_{C})$ injects the odd components into $S$ , so $o (G - S) \leq ∣ S ∣$ . $□$

Proposition 3 (Tutte's theorem, sufficiency). If $o (G - S) \leq ∣ S ∣$ for all $S \subseteq V$ , then $G$ has a perfect matching.

Proof. Taking $S = \emptyset$ gives $o (G) = 0$ , so $∣ V ∣$ is even (Proposition 1). Suppose, for contradiction, $G$ has no perfect matching, and add edges to $G$ until it is edge-maximal without a perfect matching; the Tutte condition is preserved under adding edges (adding an edge cannot increase any $o (G - S)$ ). Let $S$ be the set of vertices of degree $∣ V ∣ - 1$ . We claim $G - S$ is a disjoint union of complete graphs. If not, some component has three vertices $a, b, c$ with $ab, b c \in E$ but $a c \in / E$ , and since $b \in / S$ there is a vertex $d$ with $b d \in / E$ . By edge-maximality $G + a c$ and $G + b d$ each have perfect matchings $M_{1}, M_{2}$ ; in $M_{1} △ M_{2}$ the edges $a c$ and $b d$ lie on an alternating cycle, and rerouting along it produces a perfect matching of $G$ avoiding both new edges, a contradiction. So $G - S$ is a disjoint union of complete graphs. Each odd such clique has one leftover vertex to match into $S$ , and $o (G - S) \leq ∣ S ∣$ lets Hall match the odd cliques injectively to $S$ ; matching the remainder of each clique internally and matching $S$ 's leftover vertices among themselves (they form a clique, $∣ S ∣$ having the right parity by Proposition 1) yields a perfect matching of $G$ , contradicting the assumption. Hence $G$ had a perfect matching. $□$

Proposition 4 (Tutte-Berge formula). For every graph $G$ , the minimum number of vertices exposed over all maximum matchings equals $def (G) = max_{S} (o (G - S) - ∣ S ∣)$ .

Proof. For the lower bound, fix any matching $M$ and any $S$ . Each odd component of $G - S$ has a vertex either exposed by $M$ or matched into $S$ ; the $∣ S ∣$ vertices of $S$ absorb at most $∣ S ∣$ such, so at least $o (G - S) - ∣ S ∣$ odd components contribute an exposed vertex, giving at least $max_{S} (o (G - S) - ∣ S ∣)$ exposed vertices. For the matching upper bound, add a set $U$ of $def (G)$ new vertices, each joined to every vertex of $G$ , forming $G^{'}$ . For any $T \subseteq V (G^{'})$ : if $T \neq \supseteq U$ , then $G^{'} - T$ is connected through a vertex of $U ∖ T$ , so $o (G^{'} - T) \leq 1 \leq ∣ T ∣$ when $T \neq = \emptyset$ , and $∣ V (G^{'}) ∣$ is even so $o (G^{'}) = 0$ ; if $T \supseteq U$ , write $T = U \cup S$ and compute $o (G^{'} - T) = o (G - S) \leq ∣ S ∣ + def (G) = ∣ T ∣$ . So $G^{'}$ satisfies Tutte's condition and has a perfect matching $M^{'}$ (Proposition 3); deleting the $\leq def (G)$ edges of $M^{'}$ meeting $U$ leaves a matching of $G$ exposing at most $def (G)$ vertices. The two bounds coincide. $□$

Proposition 5 (Petersen's theorem). Every bridgeless cubic graph $G$ has a perfect matching.

Proof. Verify Tutte's condition. Fix $S \subseteq V$ and let $C_{1}, \dots, C_{k}$ be the odd components of $G - S$ , so $o (G - S) = k$ . For each $C_{i}$ , let $m_{i}$ be the number of edges between $C_{i}$ and $S$ . Summing degrees inside $C_{i}$ , $\sum_{v \in C_{i}} d (v) = 3∣ C_{i} ∣$ counts each internal edge twice and each $C_{i}$ – $S$ edge once, so $3∣ C_{i} ∣ = 2 (internal edges) + m_{i}$ ; as $∣ C_{i} ∣$ is odd, $3∣ C_{i} ∣$ is odd, forcing $m_{i}$ odd. Thus $m_{i} \geq 1$ , and $m_{i} \neq = 1$ since a lone edge from $C_{i}$ to the rest would be a bridge; hence $m_{i} \geq 3$ . The total number of $S$ – ${C_{i}}$ edges is at most $\sum_{v \in S} d (v) = 3∣ S ∣$ , so $3 k \leq \sum_{i} m_{i} \leq 3∣ S ∣$ , giving $o (G - S) = k \leq ∣ S ∣$ . By Tutte's theorem $G$ has a perfect matching. $□$

Proposition 6 (factor-critical components in the Gallai-Edmonds $D$ -set). Let $D = D (G)$ be the set of vertices exposed by some maximum matching. Every component of $G [D]$ is factor-critical.

Proof (sketch following Lovász-Plummer). Let $K$ be a component of $G [D]$ and $v \in K$ . Choose a maximum matching $M$ exposing $v$ (possible since $v \in D$ ). By the Gallai-Edmonds analysis, $M$ matches $K - v$ within $K$ : any $M$ -edge leaving $K$ would run to $A = N (D) ∖ D$ , and a counting argument on alternating paths shows every vertex of $K$ other than $v$ is matched inside $K$ , so $M$ restricted to $K$ is a perfect matching of $K - v$ . Since $v \in K$ was arbitrary and each vertex of $K$ lies in $D$ (hence is exposed by some maximum matching, which by the same argument matches the rest of $K$ internally), $K - u$ has a perfect matching for every $u \in K$ . Therefore $K$ is factor-critical. The full proof, including that the canonical $A$ is a barrier and $def (G) = c (D) - ∣ A ∣$ , runs by establishing that every maximum matching near-perfectly matches each component of $G [D]$ , matches $A$ injectively into distinct components of $G [D]$ , and perfectly matches $G [C]$ ; see ^{[Lovász-Plummer 1986 Ch. 3]}. $□$

Connections Master

Matchings I: König's theorem and Hall's marriage theorem 40.04.02. This unit is the non-bipartite continuation of the bipartite theory developed there: Tutte's condition $o (G - S) \leq ∣ S ∣$ generalises Hall's $∣ N (S) ∣ \geq ∣ S ∣$ , and the Tutte-Berge deficiency formula generalises Ore's defect form, with the odd-component count collapsing back to the neighbourhood deficiency when the graph is bipartite. Berge's augmenting-path lemma proved there is the shared starting point both halves build on; the foundational reason the two theorems split is the odd cycle, the structure on which the bipartite alternating-tree search stalls and which Edmonds' blossom contraction repairs. The regular-bipartite perfect-matching corollary of that unit is the engine of the Petersen $2$ -factor argument here.
Network flows: max-flow min-cut and the integrality theorem 40.04.09. Maximum matching is the prototype combinatorial-optimization problem whose duality this unit casts through odd components rather than cuts, and the two min-max theories meet at the integrality question: bipartite matching is a unit-capacity flow with an integral polytope by total unimodularity, while general matching needs the odd-set (blossom) inequalities precisely where flows would still be integral. The augmenting-path mechanism that drives Ford-Fulkerson is the alternating-path search that Edmonds' blossom algorithm extends past odd cycles, so the flow duality developed in the co-produced flows unit and the Tutte-Berge duality here are two faces of the same packing-covering principle, separated by the parity obstruction that flows never see.
Linear and integer programming: polytopes, duality, and total unimodularity 40.06.01. The perfect-matching polytope is a central example of an integral polytope that is not cut out by a totally unimodular system: it requires the exponentially many odd-set inequalities, and Edmonds' proof that this description is integral, together with the blossom algorithm's polynomial separation over those inequalities, is a founding result of polyhedral combinatorics. The barrier sets of Tutte-Berge are the combinatorial certificates that LP duality turns into the tight odd-set constraints, placing general matching inside the broader theory of when integer programs have integral relaxations.
Computability and complexity: the class P and polynomial-time reductions 25.03.04 pending. Edmonds' blossom algorithm is the first polynomial-time maximum-matching algorithm and the paper in which polynomial time was proposed as the formal criterion of tractable computation, so this unit is a historical root of the complexity class P. The blossom-contraction technique — shrinking an odd cycle to preserve the augmenting-path question — is the algorithmic content that the complexity unit abstracts into efficient reductions, and general matching remains the canonical example of a problem in P that resisted the naive augmenting-path approach until the odd-cycle obstruction was understood.

Historical & philosophical context Master

The non-bipartite theory began with Julius Petersen, whose 1891 paper Die Theorie der regulären Graphs (Acta Mathematica 15) ^{[Petersen 1891]} proved that every bridgeless cubic graph has a perfect matching and that every even-regular graph factors into $2$ -factors, work motivated by the factorisation of symmetric functions in invariant theory. The general criterion waited until William Thomas Tutte's 1947 paper The factorization of linear graphs (Journal of the London Mathematical Society 22) ^{[Tutte 1947]}, which characterised the graphs with a $1$ -factor by the odd-component condition now bearing his name; Tutte's original proof used the Pfaffian of a skew-symmetric matrix, tying matchings to determinants much as Frobenius had tied Hall's condition to permanents.

Claude Berge extended Tutte's theorem to the deficiency version for maximum matchings in a 1958 note (Comptes Rendus de l'Académie des Sciences 247) ^{[Berge 1958]}, giving the min-max formula for the number of exposed vertices; the result is jointly named Tutte-Berge. Tibor Gallai and Jack Edmonds independently developed the canonical structure decomposition in the early 1960s, isolating the inessential vertices $D$ , their neighbours $A$ , and the perfectly matchable remainder $C$ , with the factor-critical components that Gallai had studied as the irreducible atoms.

Edmonds' 1965 paper Paths, trees, and flowers (Canadian Journal of Mathematics 17) ^{[Edmonds 1965]} supplied the blossom algorithm, the first polynomial-time procedure for maximum matching, and in its introduction proposed polynomial running time as the definition of a "good" algorithm — the conceptual seed of the complexity class P. The same paper derived the matching polytope with its odd-set inequalities, founding polyhedral combinatorics; László Lovász and Michael Plummer's 1986 Matching Theory consolidated the ear-decomposition and Gallai-Edmonds machinery into the standard reference.

Bibliography Master

@book{Diestel2017,
  author    = {Diestel, Reinhard},
  title     = {Graph Theory},
  edition   = {5th},
  series    = {Graduate Texts in Mathematics},
  volume    = {173},
  publisher = {Springer},
  year      = {2017}
}

@book{BondyMurty2008,
  author    = {Bondy, J. A. and Murty, U. S. R.},
  title     = {Graph Theory},
  series    = {Graduate Texts in Mathematics},
  volume    = {244},
  publisher = {Springer},
  year      = {2008}
}

@book{LovaszPlummer1986,
  author    = {Lov\'asz, L\'aszl\'o and Plummer, Michael D.},
  title     = {Matching Theory},
  series    = {North-Holland Mathematics Studies},
  volume    = {121},
  publisher = {North-Holland},
  year      = {1986}
}

@book{Schrijver2003,
  author    = {Schrijver, Alexander},
  title     = {Combinatorial Optimization: Polyhedra and Efficiency},
  series    = {Algorithms and Combinatorics},
  volume    = {24},
  publisher = {Springer},
  year      = {2003}
}

@article{Petersen1891,
  author  = {Petersen, Julius},
  title   = {Die Theorie der regul\"aren Graphs},
  journal = {Acta Mathematica},
  volume  = {15},
  year    = {1891},
  pages   = {193--220}
}

@article{Tutte1947,
  author  = {Tutte, William T.},
  title   = {The factorization of linear graphs},
  journal = {Journal of the London Mathematical Society},
  volume  = {22},
  year    = {1947},
  pages   = {107--111}
}

@article{Berge1958,
  author  = {Berge, Claude},
  title   = {Sur le couplage maximum d'un graphe},
  journal = {Comptes Rendus de l'Acad\'emie des Sciences},
  volume  = {247},
  year    = {1958},
  pages   = {258--259}
}

@article{Edmonds1965,
  author  = {Edmonds, Jack},
  title   = {Paths, trees, and flowers},
  journal = {Canadian Journal of Mathematics},
  volume  = {17},
  year    = {1965},
  pages   = {449--467}
}

@article{Gallai1964,
  author  = {Gallai, Tibor},
  title   = {Maximale Systeme unabh\"angiger Kanten},
  journal = {Magyar Tudom\'anyos Akad\'emia Matematikai Kutat\'o Int\'ezet\'enek K\"ozlem\'enyei},
  volume  = {9},
  year    = {1964},
  pages   = {401--413}
}

Prerequisites

40.04.02

Tier anchors

beginner: Diestel 2017 *Graph Theory* (5th ed., Springer GTM 173) §2.2 (matchings in general graphs, the 1-factor theorem) read for the odd-component pictures and the small non-bipartite examples; West 2001 *Introduction to Graph Theory* (2nd ed., Prentice Hall) §3.3 for the odd-component counting and the pentagon/Petersen drawings
intermediate: Diestel 2017 *Graph Theory* (5th ed., Springer GTM 173) §2.2 (Tutte's 1-factor theorem and the Tutte condition, the Tutte-Berge formula, factor-critical graphs and the Gallai-Edmonds decomposition, Petersen's theorem on bridgeless cubic graphs); Bondy-Murty 2008 *Graph Theory* (Springer GTM 244) Ch. 16-17 (Tutte-Berge, Gallai-Edmonds, ear decompositions); Lovász-Plummer 1986 *Matching Theory* Ch. 3
master: Diestel 2017 *Graph Theory* (5th ed., Springer GTM 173) §2.2; Lovász-Plummer 1986 *Matching Theory* (North-Holland) Ch. 3-5 and Ch. 7 (factor-critical graphs, ear decompositions, the Gallai-Edmonds structure theorem, the matching lattice and polytope); Schrijver 2003 *Combinatorial Optimization* (Springer) Vol. A, Ch. 24-25 (Edmonds' blossom algorithm and the matching polytope); the original sources Petersen 1891, Tutte 1947, Berge 1958, Edmonds 1965, Gallai 1964

References

Diestel 2017 — Graph Theory (5th edition) · Springer Graduate Texts in Mathematics 173, 2017, §2.2 (matchings in general graphs: Tutte's 1-factor theorem, the Tutte-Berge formula, factor-critical graphs, the Gallai-Edmonds decomposition, Petersen's theorem)
Bondy, Murty 2008 — Graph Theory · Springer Graduate Texts in Mathematics 244, 2008, Ch. 16-17 (matchings in general graphs, Tutte-Berge, ear decompositions, the Gallai-Edmonds structure theorem)
Lovász, Plummer 1986 — Matching Theory · North-Holland Mathematics Studies 121, 1986, Ch. 3-5, 7 (factor-critical graphs, ear decompositions, Gallai-Edmonds, the matching lattice and the perfect-matching polytope)
Schrijver 2003 — Combinatorial Optimization: Polyhedra and Efficiency · Springer Algorithms and Combinatorics 24, 2003, Vol. A, Ch. 24-25 (Edmonds' blossom algorithm for maximum matching; the matching and perfect-matching polytopes; the odd-set / blossom inequalities)
Tutte 1947 — The factorization of linear graphs · Journal of the London Mathematical Society 22 (1947) 107-111; the 1-factor theorem: G has a perfect matching iff o(G-S) <= |S| for all S
Berge 1958 — Sur le couplage maximum d'un graphe · Comptes Rendus de l'Académie des Sciences 247 (1958) 258-259; the deficiency / max-matching formula generalising Tutte's theorem
Edmonds 1965 — Paths, trees, and flowers · Canadian Journal of Mathematics 17 (1965) 449-467; the blossom algorithm, the first polynomial-time maximum-matching algorithm, and the matching polytope
Petersen 1891 — Die Theorie der regulären Graphs · Acta Mathematica 15 (1891) 193-220; every bridgeless cubic graph has a perfect matching, and the 2-factor theorem for even-regular graphs

Estimated time

beginner: 18m
intermediate: 50m
master: 90m