40.04.02 · combinatorics / graph-theory-core

Matchings I: König's Theorem and Hall's Marriage Theorem

shipped3 tiersLean: none

Anchor (Master): Diestel 2017 *Graph Theory* (5th ed., Springer GTM 173) §2.1; Lovász-Plummer 1986 *Matching Theory* (North-Holland) Ch. 1-2 (deficiency, the König-Egerváry circle, total unimodularity, the Birkhoff polytope); Schrijver 2003 *Combinatorial Optimization* (Springer) Vol. A, Ch. 16-18; the original sources Frobenius 1917, Kőnig 1931, Hall 1935, Birkhoff 1946, von Neumann 1953

Intuition Beginner

Imagine a room with some applicants on the left and some jobs on the right. Draw a line from an applicant to a job whenever that applicant is qualified for that job. A matching is a way of handing out jobs so that no applicant gets two jobs and no job goes to two applicants: a set of the lines with no two sharing an endpoint. The basic question of matching theory is how many people you can employ at once, and when you can employ everybody.

You quickly notice that being qualified is not enough on its own. Suppose three applicants are all qualified for the same single job and nothing else. Only one of them can be hired, no matter how clever you are, because there is just one job among them to go around. The bottleneck is not any single person; it is a group of people who collectively reach too few jobs. This is the whole secret of the subject: a matching that employs everyone on one side exists exactly when no group of applicants is starved for jobs.

Hall's marriage theorem makes this precise. Picture instead some people seeking partners to marry, each willing to marry only certain others. Everyone on one side can be married off at once exactly when every group of $k$ of them is collectively willing to marry at least $k$ different people. If some group of $k$ people are jointly willing to marry only $k - 1$ others, someone is left at the altar. The condition is both necessary, which is plain, and sufficient, which is the theorem.

Visual Beginner

Picture two columns. On the left, four applicants $a_{1}, a_{2}, a_{3}, a_{4}$ ; on the right, four jobs $j_{1}, j_{2}, j_{3}, j_{4}$ . Draw the qualification lines $a_{1} - j_{1}$ , $a_{1} - j_{2}$ , $a_{2} - j_{1}$ , $a_{2} - j_{2}$ , $a_{3} - j_{3}$ , and $a_{4} - j_{3}$ . Applicants $a_{1}$ and $a_{2}$ between them reach only $j_{1}$ and $j_{2}$ , which is fine; but $a_{3}$ and $a_{4}$ together reach only the single job $j_{3}$ , so they form a starved pair.

The table beside the picture lists small groups of applicants and counts how many jobs each group can reach between them. The starved group ${a_{3}, a_{4}}$ reaches only one job, so the count $1$ falls below the group size $2$ .

group of applicants	jobs the group reaches	reaches enough?
${a_{1}}$	$j_{1}, j_{2}$ (2)	yes
${a_{1}, a_{2}}$	$j_{1}, j_{2}$ (2)	yes
${a_{3}, a_{4}}$	$j_{3}$ (1)	no

The instant one group reaches fewer jobs than its own size, employing everyone becomes impossible, and the table makes that failure visible at a glance.

Worked example Beginner

Take three students $s_{1}, s_{2}, s_{3}$ and three projects $p_{1}, p_{2}, p_{3}$ , with these preferences: $s_{1}$ will do $p_{1}$ or $p_{2}$ ; $s_{2}$ will do $p_{1}$ or $p_{3}$ ; $s_{3}$ will do only $p_{1}$ . We find an assignment giving every student a project, or show none exists.

Step 1. Start greedily. Give $s_{3}$ a project first, since $s_{3}$ is the pickiest: $s_{3}$ takes $p_{1}$ .

Step 2. Now place $s_{1}$ . Project $p_{1}$ is taken, so $s_{1}$ takes $p_{2}$ .

Step 3. Now place $s_{2}$ . Project $p_{1}$ is taken, but $s_{2}$ also accepts $p_{3}$ , which is free, so $s_{2}$ takes $p_{3}$ .

Step 4. Check the result. The assignment is $s_{1} \to p_{2}$ , $s_{2} \to p_{3}$ , $s_{3} \to p_{1}$ . Every student has a project and no project is doubled up, so all three are placed.

Step 5. Confirm with the group test. Any single student reaches at least one project; any pair reaches at least two; all three together reach $p_{1}, p_{2}, p_{3}$ , which is three. No group is starved, so a full assignment had to exist, and we found one.

What this tells us: serving the pickiest first is a sound instinct, and the group-reach test predicts in advance whether a full assignment can exist at all. If instead all three students had accepted only $p_{1}$ , the group of three would reach one project, the test would fail, and no full assignment could be built however hard you tried.

Check your understanding Beginner

Formal definition Intermediate+

Let $G = (V, E)$ be a graph. A matching is a set $M \subseteq E$ of pairwise disjoint edges — no two edges of $M$ share an endpoint ^{[Diestel 2017 §2.1]}. A vertex incident to an edge of $M$ is $M$ -saturated (or covered), and otherwise $M$ -unsaturated (or exposed). A matching is perfect if it saturates every vertex, so $∣ M ∣ = ∣ V ∣/2$ . A matching $M$ is maximal if no edge can be added while keeping it a matching, and maximum if no matching has more edges; the matching number $ν (G)$ is the size of a maximum matching. Maximal and maximum differ: in a path $v_{1} v_{2} v_{3} v_{4}$ the single middle edge $v_{2} v_{3}$ is maximal but not maximum, since ${v_{1} v_{2}, v_{3} v_{4}}$ is larger.

Given a matching $M$ , an $M$ -alternating path is a path whose edges alternate between $E ∖ M$ and $M$ . An $M$ -augmenting path is an $M$ -alternating path whose two endpoints are both $M$ -unsaturated; it necessarily begins and ends with non-matching edges and so has odd length, with one more non-matching edge than matching edge.

A graph $G$ is bipartite with parts $A, B$ when $V = A ⊔ B$ and every edge has one end in each part. For $S \subseteq V$ the neighbourhood $N (S) = ⋃_{v \in S} N (v)$ collects all vertices adjacent to some vertex of $S$ . A vertex cover is a set $U \subseteq V$ meeting every edge — each $e \in E$ has at least one endpoint in $U$ — and the vertex-cover number $τ (G)$ is the size of a smallest cover. For every graph $ν (G) \leq τ (G)$ , since a cover must spend a distinct vertex on each edge of any matching.

Definition (system of distinct representatives). Given finite sets $A_{1}, \dots, A_{n}$ , a system of distinct representatives (SDR), or transversal, is a choice of distinct elements $x_{1} \in A_{1}, \dots, x_{n} \in A_{n}$ with $x_{i} \neq = x_{j}$ for $i \neq = j$ . Modelling each $A_{i}$ as a left vertex joined to the elements of $A_{i}$ on the right, an SDR is exactly a matching saturating the left side.

Definition (doubly stochastic matrix). An $n \times n$ matrix is doubly stochastic if its entries are non-negative and every row and every column sums to $1$ . A permutation matrix is a $0/1$ doubly stochastic matrix, with exactly one $1$ in each row and column.

Counterexamples to common slips

Maximal is not maximum. A maximal matching merely admits no enlargement by a single edge; a maximum matching has the largest possible size. The path on four vertices shows the gap, and greedy edge selection only guarantees maximality.
Hall's condition is about every subset, not every vertex. Checking that each individual left vertex has a neighbour is far weaker than $∣ N (S) ∣ \geq ∣ S ∣$ for all $S \subseteq A$ . The starved pair ${a_{3}, a_{4}}$ from the Visual has both vertices with a neighbour, yet the pair reaches only one vertex.
König's min-max equality is special to bipartite graphs. In the triangle $K_{3}$ the matching number is $1$ while the vertex-cover number is $2$ , so $ν < τ$ . The equality $ν = τ$ can fail the moment an odd cycle appears.
An augmenting path must start and end exposed. An alternating path between two saturated endpoints does not enlarge the matching. Only when both endpoints are unsaturated does flipping the path along its edges gain one edge.

Key theorem with proof Intermediate+

Theorem (Berge's augmenting-path criterion and Hall's marriage theorem).

(a) Berge's lemma. A matching $M$ in any graph $G$ is maximum if and only if $G$ contains no $M$ -augmenting path.

(b) Hall's marriage theorem. A bipartite graph $G$ with parts $A, B$ has a matching saturating $A$ if and only if $∣ N (S) ∣ \geq ∣ S ∣$ for every $S \subseteq A$ .

(See ^{[Diestel 2017 §2.1]}, ^{[Hall 1935]}, ^{[Bondy-Murty 2008 Ch. 16]}.)

Proof. Part (a). Suppose $M$ admits an $M$ -augmenting path $P = v_{0} v_{1} \dots v_{2 k + 1}$ , with $v_{0}, v_{2 k + 1}$ exposed and edges alternating non-matching, matching, …, non-matching. The symmetric difference $M^{'} = M △ E (P)$ removes the $k$ matching edges of $P$ and inserts the $k + 1$ non-matching edges; every vertex still has at most one incident $M^{'}$ -edge, since interior vertices of $P$ trade one matched edge for another and the two endpoints gain their first, so $M^{'}$ is a matching with $∣ M^{'} ∣ = ∣ M ∣ + 1$ , and $M$ was not maximum. Conversely suppose $M$ is not maximum and let $M^{\*}$ be larger. Consider $H = M △ M^{\*}$ : every vertex meets at most one edge of each matching, so in $H$ every vertex has degree at most two, and $H$ is a disjoint union of paths and even cycles whose edges alternate between $M$ and $M^{\*}$ . Cycles use equally many edges of each; since $∣ M^{\*} ∣ > ∣ M ∣$ , some component is a path with more $M^{\*}$ -edges than $M$ -edges, hence a path beginning and ending with $M^{\*}$ -edges. Its endpoints are exposed by $M$ , so it is an $M$ -augmenting path in $G$ .

Part (b). Necessity is immediate: if $M$ saturates $A$ , then for any $S \subseteq A$ the partners ${M (v) : v \in S}$ are $∣ S ∣$ distinct vertices inside $N (S)$ , so $∣ N (S) ∣ \geq ∣ S ∣$ . For sufficiency assume the neighbourhood condition holds and let $M$ be a maximum matching; suppose for contradiction some $a_{0} \in A$ is exposed. Grow the set $Z$ of vertices reachable from $a_{0}$ by $M$ -alternating paths. Let $S = Z \cap A$ and $T = Z \cap B$ . Every vertex of $T$ is matched: an exposed vertex of $T$ would complete an $M$ -augmenting path from $a_{0}$ , impossible at a maximum matching by part (a). Each matched vertex of $T$ has its $M$ -partner back in $S$ , and conversely each non- $a_{0}$ vertex of $S$ entered $Z$ along a matching edge from $T$ ; so $M$ restricts to a bijection $T \to S ∖ {a_{0}}$ , giving $∣ T ∣ = ∣ S ∣ - 1$ . Every neighbour of a vertex of $S$ lies in $T$ — an edge out of $S$ extends an alternating path — so $N (S) \subseteq T$ and $∣ N (S) ∣ \leq ∣ T ∣ = ∣ S ∣ - 1 < ∣ S ∣$ , contradicting Hall's condition. Hence no vertex of $A$ is exposed and $M$ saturates $A$ . $□$

Bridge. This theorem builds toward the whole min-max theory of combinatorial optimization and appears again in every later flow, transversal, and assignment argument, because the augmenting path is the universal mechanism that certifies optimality by its own absence. The foundational reason Berge's lemma and Hall's theorem belong together is that the alternating-tree search used to prove Hall is exactly the augmenting-path search of Berge run from one exposed vertex: when it fails to reach a new exposed vertex it instead exhibits the starved set $S$ , so the obstruction to a larger matching is the obstruction Hall names. This is exactly the duality made explicit in König's theorem, where the set $S$ with $∣ N (S) ∣ < ∣ S ∣$ becomes the deficient half of a minimum vertex cover, and the alternating reachable set $Z$ is the bridge between the two. Putting these together, a matching is maximum precisely when no augmenting path survives, which generalises from bipartite SDR problems to network flows, where an augmenting path in the residual graph plays the identical role. The marriage condition is dual to a covering condition, and that duality is what the next section turns into an exact equality.

Exercises Intermediate+

Exercise 3 (medium, short-answer).

State Hall's condition for the bipartite graph with parts $A = {a_{1}, a_{2}, a_{3}}$ , $B = {b_{1}, b_{2}, b_{3}, b_{4}}$ and edges $a_{1} b_{1}, a_{1} b_{2}, a_{2} b_{1}, a_{2} b_{2}, a_{3} b_{3}$ . Does a matching saturating $A$ exist? Justify using Hall.

Hint

Test the subset ${a_{1}, a_{2}}$ and the subset ${a_{1}, a_{2}, a_{3}}$ .

Answer

Check every $S \subseteq A$ . Singletons each reach $\geq 1$ vertex. The pair ${a_{1}, a_{2}}$ reaches ${b_{1}, b_{2}}$ , so $∣ N (S) ∣ = 2 \geq 2$ . The pair ${a_{1}, a_{3}}$ reaches ${b_{1}, b_{2}, b_{3}}$ , size $3 \geq 2$ ; similarly ${a_{2}, a_{3}}$ . The full set reaches ${b_{1}, b_{2}, b_{3}}$ , size $3 \geq 3$ . Hall's condition holds for all subsets, so a matching saturating $A$ exists; for instance $a_{1} b_{1}, a_{2} b_{2}, a_{3} b_{3}$ . Rubric: full credit for verifying the binding subsets and exhibiting a saturating matching.

Exercise 4 (medium, short-answer).

Deduce from Hall's theorem that every $k$ -regular bipartite graph (with $k \geq 1$ ) has a perfect matching.

Hint

Count edges between $S$ and $N (S)$ two ways: from the $S$ side they number $k ∣ S ∣$ , and they all land in $N (S)$ .

Answer

Let $G$ be $k$ -regular bipartite with parts $A, B$ . Counting edges by endpoints, $k ∣ A ∣ = ∣ E ∣ = k ∣ B ∣$ , so $∣ A ∣ = ∣ B ∣$ ; a matching saturating $A$ is then perfect. For $S \subseteq A$ , the edges leaving $S$ number exactly $k ∣ S ∣$ and each lands in $N (S)$ ; since each vertex of $N (S)$ absorbs at most $k$ of them, $k ∣ S ∣ \leq k ∣ N (S) ∣$ , hence $∣ N (S) ∣ \geq ∣ S ∣$ . Hall's condition holds, so a matching saturating $A$ exists, and by $∣ A ∣ = ∣ B ∣$ it is perfect. Rubric: full credit for the double count giving Hall's inequality and the equal-parts observation.

Exercise 6 (medium, symbolic).

Let $M$ be a matching and $P$ an $M$ -augmenting path. Prove that $M^{'} = M △ E (P)$ is a matching with $∣ M^{'} ∣ = ∣ M ∣ + 1$ .

Hint

Track the degree of each vertex in $M^{'}$ : interior vertices of $P$ , endpoints of $P$ , and vertices off $P$ .

Answer

Write $P = v_{0} v_{1} \dots v_{2 k + 1}$ with $v_{0}, v_{2 k + 1}$ exposed; its edges alternate non- $M$ , $M$ , …, non- $M$ , so $P$ has $k$ edges in $M$ and $k + 1$ outside. Taking $M^{'} = M △ E (P)$ deletes those $k$ matched edges and adds the $k + 1$ unmatched ones. A vertex off $P$ keeps its $M$ -edges untouched, so it meets at most one $M^{'}$ -edge. An interior vertex $v_{i}$ ( $1 \leq i \leq 2 k$ ) met exactly one $M$ -edge of $P$ and one non- $M$ -edge of $P$ ; $M^{'}$ swaps which of the two it uses, leaving degree one. Each endpoint $v_{0}, v_{2 k + 1}$ was exposed and now meets exactly the one new edge of $P$ . So every vertex has $M^{'}$ -degree at most one and $M^{'}$ is a matching, with $∣ M^{'} ∣ = ∣ M ∣ - k + (k + 1) = ∣ M ∣ + 1$ . Rubric: full credit for the per-vertex degree bookkeeping and the edge count.

Exercise 7 (hard, short-answer).

Prove König's theorem from Hall's theorem: in a bipartite graph $G$ with parts $A, B$ , the maximum matching size equals the minimum vertex-cover size, $ν (G) = τ (G)$ .

Hint

The inequality $ν \leq τ$ is easy. For the reverse, let $d = max_{S \subseteq A} (∣ S ∣ - ∣ N (S) ∣)$ be the deficiency; build a cover of size $∣ A ∣ - d$ and a matching of that size.

Answer

Always $ν \leq τ$ , since a cover must use a distinct vertex for each edge of a matching. For the reverse, let $d = max_{S \subseteq A} (∣ S ∣ - ∣ N (S) ∣) \geq 0$ (the empty set gives $0$ ), attained at $S_{0}$ . Defect Hall gives $ν = ∣ A ∣ - d$ . Build a cover $U = (A ∖ S_{0}) \cup N (S_{0})$ . It covers every edge: an edge with left end in $A ∖ S_{0}$ is covered there; an edge with left end in $S_{0}$ has its right end in $N (S_{0}) \subseteq U$ . So $τ \leq ∣ U ∣ = (∣ A ∣ - ∣ S_{0} ∣) + ∣ N (S_{0}) ∣ = ∣ A ∣ - (∣ S_{0} ∣ - ∣ N (S_{0}) ∣) = ∣ A ∣ - d = ν$ . Combined with $ν \leq τ$ this forces $ν = τ$ . (The defect form itself follows from Hall applied to $A$ after adding $d$ dummy right-vertices each joined to all of $A$ , which restores Hall's condition.) Rubric: full credit for the cover construction matching the defect value and the two inequalities closing.

Exercise 8 (hard, short-answer).

A Latin rectangle is an $r \times n$ array ( $r < n$ ) with entries from ${1, \dots, n}$ such that no symbol repeats in any row or any column. Prove that any Latin rectangle can be extended by one more row to an $(r + 1) \times n$ Latin rectangle.

Hint

For column $j$ , let $A_{j}$ be the set of symbols not yet used in that column. Find a system of distinct representatives for $A_{1}, \dots, A_{n}$ via Hall; each column-set has size $n - r$ .

Answer

For each column $j$ let $A_{j} \subseteq {1, \dots, n}$ be the symbols absent from column $j$ ; since $r$ symbols are present, $∣ A_{j} ∣ = n - r$ . A valid new row chooses, for each column $j$ , a symbol from $A_{j}$ , all distinct — an SDR for $A_{1}, \dots, A_{n}$ . Model this as a bipartite graph: columns on the left, symbols on the right, edge $j \sim c$ iff $c \in A_{j}$ . Each symbol $c$ appears in exactly $r$ of the rows, hence is absent from exactly $n - r$ columns, so every symbol has degree $n - r$ on the right; every column has degree $n - r$ on the left. The graph is $(n - r)$ -regular bipartite, so by Exercise 4 it has a perfect matching, which is the required SDR. Filling the new row from this matching repeats no symbol in any column (the SDR is column-indexed and distinct) nor in any row (distinct symbols), extending the rectangle. Rubric: full credit for the regular-bipartite SDR construction and the verification of both Latin constraints.

Advanced results Master

Theorem (König's theorem and the König-Egerváry duality). In a bipartite graph $G$ , $ν (G) = τ (G)$ , and dually the maximum independent set has size $∣ V ∣ - ν (G)$ (the Gallai identity, since the complement of a vertex cover is an independent set). (Kőnig ^{[König 1931]}; Diestel ^{[Diestel 2017 §2.1]}.) The matching polytope of a bipartite graph is exactly the set of non-negative edge weightings $x$ with $\sum_{e ∋ v} x_{e} \leq 1$ at each vertex: its incidence matrix is totally unimodular because the rows split into the two colour classes and every column has one $1$ in each class, so every square submatrix has determinant in ${0, \pm 1}$ . Hence the linear-programming relaxation has integral vertices, and the LP-duality between maximum fractional matching and minimum fractional cover specialises to König's integral equality — the polyhedral proof that runs parallel to the augmenting-path proof.

Theorem (defect version of Hall). In a bipartite graph with parts $A, B$ , the maximum number of vertices of $A$ that can be saturated by a matching is $$ |A| - \max_{S \subseteq A}\big(|S| - |N(S)|\big). $$ (Ore's defect formula; Diestel ^{[Diestel 2017 §2.1]}.) The quantity $def (G) = max_{S} (∣ S ∣ - ∣ N (S) ∣)$ is the deficiency; Hall's theorem is the case $def = 0$ . The formula follows by padding $B$ with $def$ universal dummy vertices to restore Hall, matching, then deleting the dummies.

Theorem (Birkhoff-von Neumann). The doubly stochastic $n \times n$ matrices form a convex polytope whose vertices are exactly the $n!$ permutation matrices; equivalently, every doubly stochastic matrix is a convex combination of permutation matrices. (Birkhoff ^{[Birkhoff 1946]}.) Given a doubly stochastic $D$ , form the bipartite graph on rows and columns with an edge $i \sim j$ whenever $D_{ij} > 0$ . For any set $S$ of rows, the column-sum over $N (S)$ is at least the total mass $∣ S ∣$ of those rows, so $∣ N (S) ∣ \geq ∣ S ∣$ and Hall yields a perfect matching, hence a permutation $σ$ with $D_{iσ (i)} > 0$ for all $i$ . Subtracting $λ P_{σ}$ for $λ = min_{i} D_{iσ (i)}$ keeps the matrix non-negative and doubly substochastic with the same row/column ratio, strictly reduces the support, and after rescaling repeats; induction on the support size writes $D = \sum_{k} λ_{k} P_{σ_{k}}$ with $λ_{k} \geq 0$ , $\sum_{k} λ_{k} = 1$ .

Theorem (the Hungarian-method viewpoint and weighted matching). The maximum-weight perfect matching in a complete bipartite graph $K_{n, n}$ with weights $w_{ij}$ is computed by the Hungarian algorithm, which maintains a feasible dual labelling $u_{i} + v_{j} \geq w_{ij}$ and grows the equality subgraph $G_{=}$ where $u_{i} + v_{j} = w_{ij}$ until $G_{=}$ admits a perfect matching, certified optimal by complementary slackness. (Schrijver ^{[Schrijver 2003 Ch. 17-18]}.) The unweighted König theorem is the all-weights-equal case, the dual labelling collapses to the vertex cover, and the alternating-tree growth is precisely the augmenting-path search of Berge's lemma run inside $G_{=}$ .

Synthesis. These results are a single min-max principle seen at increasing depth, and putting these together the bipartite matching problem becomes the prototype of combinatorial duality, where a maximum packing equals a minimum cover and an obstruction set is also a certificate. The central insight is that Hall's neighbourhood deficiency, König's minimum cover, and the LP dual labelling of the Hungarian method are three readings of one inequality $∣ N (S) ∣ \geq ∣ S ∣$ : the deficient set $S$ that blocks a saturating matching is exactly the deficient half of a minimum cover and exactly the tight dual constraint, so the augmenting-path search either enlarges the matching or hands back the obstruction. This is exactly the principle that total unimodularity of the bipartite incidence matrix makes the LP relaxation integral, so the fractional and integral optima coincide and König's equality is the strong-duality theorem read combinatorially. The marriage theorem is dual to a covering theorem, and the same duality generalises: it is the bipartite, cardinality-balanced shadow of the max-flow min-cut theorem, where augmenting paths in a residual network replace alternating paths, and it is the order-theoretic cousin of Dilworth's theorem, where a minimum chain cover of a poset equals a maximum antichain through König on the comparability bipartite graph. The Birkhoff-von Neumann theorem is the geometric face of the same fact, identifying the permutation matrices as the extreme points that Hall's perfect matchings supply, so the foundational reason doubly stochastic matrices average permutations is that their positive support always satisfies the marriage condition.

Full proof set Master

Proposition 1 (Berge's augmenting-path criterion). A matching $M$ in a graph $G$ is maximum if and only if $G$ has no $M$ -augmenting path.

Proof. If $P$ is an $M$ -augmenting path, then $M △ E (P)$ is a matching of size $∣ M ∣ + 1$ (Exercise 6), so $M$ is not maximum. Conversely, suppose $M$ is not maximum and fix a matching $M^{\*}$ with $∣ M^{\*} ∣ > ∣ M ∣$ . In the symmetric difference $H = M △ M^{\*}$ every vertex is incident to at most one edge of each matching, hence has degree at most two in $H$ ; therefore each connected component of $H$ is a single vertex, a path, or a cycle, and along any such path or cycle the edges alternate between $M$ and $M^{\*}$ (two consecutive $M$ -edges would share a vertex). Each cycle has even length with equal numbers of $M$ - and $M^{\*}$ -edges; each path has $M$ - and $M^{\*}$ -edge counts differing by at most one. As $∣ M^{\*} ∣ > ∣ M ∣$ , summing over components forces some path component with strictly more $M^{\*}$ - than $M$ -edges, which therefore starts and ends with $M^{\*}$ -edges. Its two endpoints are not met by $M$ within $H$ , and they are not met by $M$ outside $H$ either (an $M$ -edge at an endpoint would lie in $H$ ), so they are $M$ -exposed. This component is an $M$ -augmenting path. $□$

Proposition 2 (Hall's marriage theorem). A bipartite graph $G$ with parts $A, B$ has a matching saturating $A$ if and only if $∣ N (S) ∣ \geq ∣ S ∣$ for all $S \subseteq A$ .

Proof. (Necessity) If $M$ saturates $A$ , then for $S \subseteq A$ the $M$ -partners of the vertices of $S$ are $∣ S ∣$ distinct vertices lying in $N (S)$ , so $∣ N (S) ∣ \geq ∣ S ∣$ .

(Sufficiency) Assume the condition and let $M$ be a maximum matching. Suppose some $a_{0} \in A$ is exposed. Let $Z$ be all vertices reached from $a_{0}$ by $M$ -alternating paths (paths starting with a non- $M$ edge), and set $S = Z \cap A$ , $T = Z \cap B$ . No vertex of $T$ is exposed: an exposed $b \in T$ would give an $M$ -augmenting $a_{0}$ – $b$ path, contradicting maximality via Proposition 1. Thus each $b \in T$ is matched, and its partner lies in $S$ (the alternating path to $b$ ends with a non- $M$ edge, so continuing along $b$ 's $M$ -edge returns to $A$ inside $Z$ ). Conversely every vertex of $S ∖ {a_{0}}$ was entered along an $M$ -edge from $T$ . Hence $M$ matches $T$ bijectively onto $S ∖ {a_{0}}$ , giving $∣ T ∣ = ∣ S ∣ - 1$ . Finally $N (S) \subseteq T$ : a neighbour $b$ of some $s \in S$ is reached by appending the edge $s b$ to an alternating path ending at $s$ , so $b \in Z \cap B = T$ . Therefore $∣ N (S) ∣ \leq ∣ T ∣ = ∣ S ∣ - 1 < ∣ S ∣$ , contradicting the hypothesis. So $A$ has no exposed vertex and $M$ saturates $A$ . $□$

Proposition 3 (König's theorem). For bipartite $G$ , $ν (G) = τ (G)$ .

Proof. The bound $ν \leq τ$ holds in every graph: a vertex cover contains an endpoint of each of the $ν$ disjoint matching edges, and these endpoints are distinct, so $τ \geq ν$ . For $τ \leq ν$ , set $d = max_{S \subseteq A} (∣ S ∣ - ∣ N (S) ∣) \geq 0$ , attained at some $S_{0}$ . By the defect formula (Proposition 4) the maximum matching saturates $∣ A ∣ - d$ vertices of $A$ , so $ν = ∣ A ∣ - d$ . Put $U = (A ∖ S_{0}) \cup N (S_{0})$ . Every edge $e = ab$ ( $a \in A$ , $b \in B$ ) is covered: if $a \in / S_{0}$ then $a \in U$ ; if $a \in S_{0}$ then $b \in N (S_{0}) \subseteq U$ . Thus $U$ is a cover with $∣ U ∣ = (∣ A ∣ - ∣ S_{0} ∣) + ∣ N (S_{0}) ∣ = ∣ A ∣ - (∣ S_{0} ∣ - ∣ N (S_{0}) ∣) = ∣ A ∣ - d = ν$ . Hence $τ \leq ν$ , and equality follows. $□$

Proposition 4 (defect form of Hall). In bipartite $G$ with parts $A, B$ , the maximum number of $A$ -vertices a matching can saturate equals $∣ A ∣ - max_{S \subseteq A} (∣ S ∣ - ∣ N (S) ∣)$ .

Proof. Let $d = max_{S} (∣ S ∣ - ∣ N (S) ∣)$ . No matching saturates more than $∣ A ∣ - d$ vertices of $A$ : if a witness set $S$ has $∣ N (S) ∣ = ∣ S ∣ - d^{'}$ with $d^{'} \leq d$ , at most $∣ N (S) ∣ = ∣ S ∣ - d^{'}$ vertices of $S$ are matched, so at least $d^{'}$ , and in particular at least are unsaturated for the maximizing $S$ giving $d$ ; precisely, the $S$ attaining $d$ leaves $\geq d$ of its vertices exposed, so saturated $A$ -vertices number $\leq ∣ A ∣ - d$ . For the achievability, adjoin $d$ new vertices $b_{1}^{\*}, \dots, b_{d}^{\*}$ to $B$ , each joined to every vertex of $A$ , forming $G^{+}$ . For any $S \subseteq A$ , $∣ N_{G^{+}} (S) ∣ = ∣ N_{G} (S) ∣ + d \geq (∣ S ∣ - d) + d = ∣ S ∣$ , so Hall's condition holds in $G^{+}$ and $G^{+}$ has a matching $M^{+}$ saturating $A$ . Deleting the at most $d$ edges of $M^{+}$ meeting the dummy vertices leaves a matching in $G$ saturating at least $∣ A ∣ - d$ vertices of $A$ . The two bounds coincide. $□$

Proposition 5 (Birkhoff-von Neumann). Every $n \times n$ doubly stochastic matrix $D$ is a convex combination of permutation matrices.

Proof. Induct on the number $s$ of strictly positive entries of $D$ . A doubly stochastic matrix has $s \geq n$ (each of the $n$ rows sums to $1 > 0$ ). Form the bipartite graph $H$ on rows ${1, \dots, n}$ and columns ${1, \dots, n}$ with edge $i \sim j$ iff $D_{ij} > 0$ . For $S$ a set of rows, the entries of $D$ in those rows total $∣ S ∣$ (each row sums to $1$ ) and are confined to columns in $N (S)$ , where the total over all rows is $∣ N (S) ∣$ (each column sums to $1$ ); hence $∣ S ∣ \leq ∣ N (S) ∣$ . By Hall (Proposition 2) $H$ has a perfect matching, a permutation $σ$ with $D_{iσ (i)} > 0$ for all $i$ . Let $λ = min_{i} D_{iσ (i)} \in (0, 1]$ . If $λ = 1$ then $D = P_{σ}$ is itself a permutation matrix. Otherwise $D^{'} = (D - λ P_{σ}) / (1 - λ)$ is non-negative, has all row and column sums equal to $(1 - λ) / (1 - λ) = 1$ , hence is doubly stochastic, and has strictly fewer positive entries than $D$ (the index achieving the minimum became $0$ ). By induction $D^{'} = \sum_{k} μ_{k} P_{σ_{k}}$ with $μ_{k} \geq 0$ , $\sum_{k} μ_{k} = 1$ , so $D = λ P_{σ} + (1 - λ) \sum_{k} μ_{k} P_{σ_{k}}$ is the desired convex combination. The permutation matrices are extreme points because each has a $1$ that no nontrivial average of distinct doubly stochastic matrices can produce without one summand having a $0$ where $P_{σ}$ has a $1$ . $□$

Connections Master

Graphs, basic invariants, and the foundational lemmas 40.04.01. Matchings are subgraphs of maximum degree one, so the vertex, edge, degree, and bipartite vocabulary established there is exactly the language a matching is phrased in; the no-odd-cycle characterisation of bipartiteness from that unit is the structural hypothesis that makes König's equality $ν = τ$ hold and fail the moment an odd cycle appears. The handshake double-count reappears here as the edge-balance $k ∣ A ∣ = k ∣ B ∣$ that forces equal parts in a regular bipartite graph, and the alternating-path search is the matching-tuned version of the walk-and-path distinction defined there.
Tutte's theorem and matchings in general graphs 40.04.03. This unit is the bipartite half of matching theory; the sequel removes the bipartite hypothesis and replaces Hall's neighbourhood condition with Tutte's $1$ -factor condition $o (G - S) \leq ∣ S ∣$ on odd components, with the Tutte-Berge defect formula generalising Ore's defect form proved here. The foundational reason the two theorems split is the odd cycle: the alternating-tree argument that proves Hall stalls at odd structures, and Tutte's barrier sets and the blossom contraction of Edmonds are exactly the machinery that repairs that stall, so this unit's Berge's lemma is the shared starting point both halves build on.
Network flows: max-flow min-cut and the integrality theorem 40.04.09. Bipartite maximum matching is the unit-capacity flow problem with a source feeding $A$ and a sink drained by $B$ , the augmenting paths of Berge's lemma are the residual augmenting paths of Ford-Fulkerson, and König's $ν = τ$ duality is the integral case of max-flow min-cut. The total unimodularity that makes the matching LP integral is the same property that makes the flow LP integral, so the min-max theorems of this unit are the cardinality-balanced specialisation of the flow duality developed there.
Dilworth's theorem and the structure of partial orders 40.02.01. Dilworth's theorem — a finite poset's minimum chain cover equals its maximum antichain — is König's theorem applied to the bipartite comparability graph built from the poset's strict order, where a chain cover corresponds to a matching and an antichain to an independent set. The marriage condition and the defect formula proved here are the engine of that deduction, placing matchings and order theory inside one min-max family, and the Mirsky dual (minimum antichain cover equals maximum chain) is the transpose of the same duality.

Historical & philosophical context Master

The neighbourhood condition predates its graph-theoretic form. Georg Frobenius, studying when a determinant of a structured matrix vanishes identically, proved in 1917 (Über zerlegbare Determinanten, Sitzungsberichte der Preußischen Akademie) ^{[Frobenius 1917]} a criterion equivalent to the existence of a nonzero term in a permanent, which is the existence of a system of distinct representatives — Hall's condition in determinant language. Dénes Kőnig, building the first systematic theory of graphs, proved in 1931 (Gráfok és mátrixok, Matematikai és Fizikai Lapok 38) ^{[König 1931]} that in a bipartite graph the maximum matching equals the minimum vertex cover, the min-max duality now bearing his name, with Jenő Egerváry supplying the weighted generalisation the same year.

Philip Hall stated and proved the marriage theorem in 1935 (On representatives of subsets, Journal of the London Mathematical Society 10) ^{[Hall 1935]}, framed as the question of choosing distinct representatives from a family of subsets; the "marriage" interpretation, pairing each member of one set with an acceptable partner, became the standard pedagogical image. The transversal theory that grew from Hall's paper — through the work of Rado, Mirsky, and Perfect — recast SDRs as independent sets in a transversal matroid, embedding matching into matroid theory.

The doubly stochastic connection was crystallised by Garrett Birkhoff in 1946 (Tres observaciones sobre el álgebra lineal, Universidad Nacional de Tucumán Revista A 5) ^{[Birkhoff 1946]}, who identified the permutation matrices as the vertices of the polytope of doubly stochastic matrices; John von Neumann gave an independent proof in 1953 in the context of the assignment problem and game theory, and the algorithmic side matured into Harold Kuhn's 1955 Hungarian method, named for its debt to Kőnig and Egerváry. Jack Edmonds's 1965 polynomial blossom algorithm for general matchings later closed the gap left by the bipartite case treated here.

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{Hall1935,
  author  = {Hall, Philip},
  title   = {On representatives of subsets},
  journal = {Journal of the London Mathematical Society},
  volume  = {10},
  year    = {1935},
  pages   = {26--30}
}

@article{Konig1931,
  author  = {K\H{o}nig, D\'enes},
  title   = {Gr\'afok \'es m\'atrixok},
  journal = {Matematikai \'es Fizikai Lapok},
  volume  = {38},
  year    = {1931},
  pages   = {116--119}
}

@article{Frobenius1917,
  author  = {Frobenius, Georg},
  title   = {\"Uber zerlegbare Determinanten},
  journal = {Sitzungsberichte der Preu{\ss}ischen Akademie der Wissenschaften},
  year    = {1917},
  pages   = {274--277}
}

@article{Birkhoff1946,
  author  = {Birkhoff, Garrett},
  title   = {Tres observaciones sobre el \'algebra lineal},
  journal = {Universidad Nacional de Tucum\'an Revista A},
  volume  = {5},
  year    = {1946},
  pages   = {147--150}
}

@article{Kuhn1955,
  author  = {Kuhn, Harold W.},
  title   = {The Hungarian method for the assignment problem},
  journal = {Naval Research Logistics Quarterly},
  volume  = {2},
  year    = {1955},
  pages   = {83--97}
}

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

Prerequisites

40.04.01

Tier anchors

beginner: Diestel 2017 *Graph Theory* (5th ed., Springer GTM 173) §2.1 (matchings, augmenting paths, the marriage theorem) read for the dots-and-lines pictures and the small bipartite examples; West 2001 *Introduction to Graph Theory* (2nd ed., Prentice Hall) §3.1 for the job-assignment and dance-pairing framing of Hall's condition
intermediate: Diestel 2017 *Graph Theory* (5th ed., Springer GTM 173) §2.1 (Berge's augmenting-path criterion, Hall's marriage theorem and its defect form, König's min-max duality, the Hungarian-method viewpoint); Bondy-Murty 2008 *Graph Theory* (Springer GTM 244) Ch. 16 (matchings in bipartite graphs); Lovász-Plummer 1986 *Matching Theory* Ch. 1
master: Diestel 2017 *Graph Theory* (5th ed., Springer GTM 173) §2.1; Lovász-Plummer 1986 *Matching Theory* (North-Holland) Ch. 1-2 (deficiency, the König-Egerváry circle, total unimodularity, the Birkhoff polytope); Schrijver 2003 *Combinatorial Optimization* (Springer) Vol. A, Ch. 16-18; the original sources Frobenius 1917, Kőnig 1931, Hall 1935, Birkhoff 1946, von Neumann 1953

References

Diestel 2017 — Graph Theory (5th edition) · Springer Graduate Texts in Mathematics 173, 2017, §2.1 (matchings in bipartite graphs: augmenting paths, the marriage theorem, the König duality and its applications)
Bondy, Murty 2008 — Graph Theory · Springer Graduate Texts in Mathematics 244, 2008, Ch. 16 (matchings, Berge's theorem, the Hungarian algorithm, König and Hall)
Lovász, Plummer 1986 — Matching Theory · North-Holland Mathematics Studies 121, 1986, Ch. 1-2 (bipartite matchings, deficiency, the König-Egerváry theorem, doubly stochastic matrices)
Schrijver 2003 — Combinatorial Optimization: Polyhedra and Efficiency · Springer Algorithms and Combinatorics 24, 2003, Vol. A, Ch. 16-18 (cardinality bipartite matching, the assignment problem, total unimodularity of the incidence matrix)
Hall 1935 — On representatives of subsets · Journal of the London Mathematical Society 10 (1935) 26-30; the marriage condition for a system of distinct representatives
König 1931 — Gráfok és mátrixok · Matematikai és Fizikai Lapok 38 (1931) 116-119; max matching = min vertex cover in bipartite graphs
Frobenius 1917 — Über zerlegbare Determinanten · Sitzungsberichte der Preußischen Akademie der Wissenschaften (1917) 274-277; the determinant/permanent precursor of Hall's condition
Birkhoff 1946 — Tres observaciones sobre el algebra lineal · Universidad Nacional de Tucumán Revista A 5 (1946) 147-150; doubly stochastic matrices as convex combinations of permutation matrices

Estimated time

beginner: 18m
intermediate: 48m
master: 86m