regular_bipartite_has_perfect_matching
Every d-regular bipartite simple graph on a finite vertex set, with degree d > 0, has a perfect matching.
Statement
theorem regular_bipartite_has_perfect_matching {V : Type*} [Fintype V] (G : SimpleGraph V) {d : ℕ} (hd : 0 < d) (hreg : G.IsRegularOfDegree d) (hbip : G.IsBipartite) : ∃ M : SimpleGraph.Subgraph G, M.IsPerfectMatching
- Formalizes
- Diestel, Graph Theory, Corollary 2.1.3
- Verified
- 06 Oct 2026
- Axioms
Classical.choiceQuot.soundpropext- Used by 2
- equal_marginal_balanced_high_count_allocationsFor at least two agents, k at least two, and n*k chores, each agent has an arbitrary set of high chores. There are n allocations such that…
- regular_bipartite_decompose_perfect_matchingsEvery d-regular finite bipartite simple graph decomposes into d spanning one-regular subgraphs: every edge appears in exactly one of them.
Read back from the Lean
For any finite type V, any simple graph G on V, and any natural number d such that 0 < d, if G is regular of degree d (every vertex in V has degree d) and G is bipartite (2-colorable), then there exists a subgraph M of G that is a perfect matching of G (that is, M spans all vertices of V and every vertex has degree 1 in M).
Written by a model that saw only the Lean, never the English above. If the two disagree, that is worth a challenge.
The proof, explained
To show that every d-regular bipartite graph with d > 0 has a perfect matching, we verify Hall's marriage condition: every vertex subset S satisfies |S| ≤ |N(S)|. Double counting the edges between S and its neighborhood T = N(S) shows that |S| * d = ∑_{u ∈ S} deg_T(u) = ∑_{v ∈ T} deg_S(v) ≤ |T| * d. Since d > 0, dividing by d yields |S| ≤ |T|. Hall's marriage theorem for bipartite graphs then guarantees the existence of a perfect matching.
Define the neighborhood T of S and note that every vertex has degree d.
Let T = ⋃ u ∈ S, N(u) be the union of the neighborhoods of all vertices in S. By the regularity of G, every vertex v has degree d, so each neighbor finset N(v) has cardinality d.
uses
card_neighborFinset_eq_degreelet T := S.biUnion (fun x => G.neighborFinset x) have h_deg (v : V) : #(G.neighborFinset v) = d := by rw [card_neighborFinset_eq_degree] exact hreg v
For every vertex u ∈ S, the number of its neighbors in T is exactly d.
By definition, `bipartiteAbove G.Adj T u` is the set of neighbors of u that lie in T. Since u ∈ S, every neighbor of u is in T by definition of T as the union of neighborhoods of vertices in S. Hence this set is the entire neighborhood N(u), which has cardinality d.
uses
Finset.mem_biUnionhave h_above (u : V) (hu : u ∈ S) : #(bipartiteAbove G.Adj T u) = d := by have : bipartiteAbove G.Adj T u = G.neighborFinset u := by ext v simp only [bipartiteAbove, mem_filter, mem_neighborFinset] constructor · intro ⟨_, hadj⟩ exact hadj · intro hadj refine ⟨?_, hadj⟩ rw [Finset.mem_biUnion] exact ⟨u, hu, G.mem_neighborFinset u v |>.mpr hadj⟩ rw [this, h_deg]
For every vertex v ∈ V, the number of its neighbors in S is at most d.
The set `bipartiteBelow G.Adj S v` consists of the neighbors of v that lie in S. This is a subset of the full neighborhood N(v). Because |N(v)| = d, the cardinality of this subset is at most d.
uses
Finset.card_le_cardhave h_below (v : V) : #(bipartiteBelow G.Adj S v) ≤ d := by have : bipartiteBelow G.Adj S v ⊆ G.neighborFinset v := by intro u hu simp only [bipartiteBelow, mem_filter] at hu simp only [mem_neighborFinset] exact hu.2.symm exact (Finset.card_le_card this).trans (h_deg v).le
The sum over u ∈ S of the number of its neighbors in T equals |S| * d.
Since each vertex u ∈ S has exactly d neighbors in T, summing this constant value d over all |S| vertices in S gives |S| * d.
uses
sum_congrhave h_sum_above : ∑ u ∈ S, #(bipartiteAbove G.Adj T u) = #S * d := by rw [sum_congr rfl h_above] simp
The sum over v ∈ T of the number of its neighbors in S is at most |T| * d.
Each vertex v ∈ T has at most d neighbors in S. Summing these upper bounds over all vertices in T gives at most ∑ v ∈ T, d = |T| * d.
uses
sum_le_sumhave h_sum_below : ∑ v ∈ T, #(bipartiteBelow G.Adj S v) ≤ #T * d := by calc ∑ v ∈ T, #(bipartiteBelow G.Adj S v) _ ≤ ∑ v ∈ T, d := sum_le_sum fun v _ => h_below v _ = #T * d := by simp
The cardinality of S is at most the cardinality of its neighborhood T.
By double counting edges between S and T (`sum_card_bipartiteAbove_eq_sum_card_bipartiteBelow`), the sum of degrees from S into T equals the sum of degrees from T into S. Therefore |S| * d ≤ |T| * d. Because d > 0, dividing by d yields |S| ≤ |T|.
uses
sum_card_bipartiteAbove_eq_sum_card_bipartiteBelow,Nat.le_of_mul_le_mul_righthave h_eq := sum_card_bipartiteAbove_eq_sum_card_bipartiteBelow G.Adj (s := S) (t := T) have h_mul_le : #S * d ≤ #T * d := by rw [← h_sum_above, h_eq] exact h_sum_below exact Nat.le_of_mul_le_mul_right h_mul_le hd
For any subset s of vertices, |s| ≤ |N(s)|.
First, the finset corresponding to the set union ⋃ x ∈ s, N(x) is identified with the finset bi-union over the finset coercion of s. Rewriting the set cardinalities (`ncard`) to finset cardinalities via `Set.ncard_eq_toFinset_card'`, the inequality follows from the finset version `regular_bipartite_has_perfect_matching_card_le_card_biUnion`.
uses
Set.ncard_eq_toFinset_card',regular_bipartite_has_perfect_matching_card_le_card_biUnionhave h_eq : (⋃ x ∈ s, G.neighborSet x).toFinset = s.toFinset.biUnion (fun x => G.neighborFinset x) := by ext v simp rw [Set.ncard_eq_toFinset_card' s, Set.ncard_eq_toFinset_card' _, h_eq] exact regular_bipartite_has_perfect_matching_card_le_card_biUnion G hd hreg s.toFinset
The graph G has a perfect matching.
The assumption that G is bipartite yields a 2-partition of the vertices into independent sets. By Hall's marriage theorem for bipartite graphs (`exists_isPerfectMatching_of_forall_ncard_le`), G has a perfect matching because Hall's condition |s| ≤ |N(s)| holds for every vertex subset s by `regular_bipartite_has_perfect_matching_ncard_le_ncard_biUnion`.
uses
exists_isPerfectMatching_of_forall_ncard_le,regular_bipartite_has_perfect_matching_ncard_le_ncard_biUnionobtain ⟨p₁, p₂, hbipW⟩ := hbip.exists_isBipartiteWith exact exists_isPerfectMatching_of_forall_ncard_le hbipW (fun s => regular_bipartite_has_perfect_matching_ncard_le_ncard_biUnion G hd hreg s)
card_neighborFinset_eq_degree- The cardinality of the neighbor finset of a vertex equals its degree.
Finset.mem_biUnion- An element belongs to a finset union ⋃ a ∈ s, t a if and only if it belongs to t a for some a ∈ s.
Finset.card_le_card- If s ⊆ t for finite sets s and t, then |s| ≤ |t|.
sum_congr- Two sums over finite sets are equal if their index sets are equal and their terms are equal at every element.
sum_le_sum- A sum of terms is bounded by the sum of term-by-term upper bounds.
sum_card_bipartiteAbove_eq_sum_card_bipartiteBelow- For any binary relation between finite sets s and t, the sum over a ∈ s of the number of related elements in t equals the sum over b ∈ t of the number of related elements in s.
Nat.le_of_mul_le_mul_right- If a * c ≤ b * c and 0 < c, then a ≤ b for natural numbers.
Set.ncard_eq_toFinset_card'- The set cardinality (`ncard`) of a finite set equals the cardinality of its coercion to a `Finset`.
regular_bipartite_has_perfect_matching_card_le_card_biUnion- In a d-regular graph on a finite vertex set with d > 0, any finset S satisfies |S| ≤ |N(S)|.
exists_isPerfectMatching_of_forall_ncard_le- A locally finite bipartite graph has a perfect matching if Hall's condition |s| ≤ |N(s)| holds for every subset of vertices s.
regular_bipartite_has_perfect_matching_ncard_le_ncard_biUnion- In a d-regular graph on a finite vertex set with d > 0, every subset s of vertices satisfies |s| ≤ |N(s)|.
- Mathlib's formulation of Hall's marriage theorem for perfect matchings (`exists_isPerfectMatching_of_forall_ncard_le`) is stated in terms of `Set.ncard` rather than `Finset.card`, so the counting argument is first proved for finite sets (`Finset`) and then converted to arbitrary subsets (`Set`).
Written by a model (gemini-3.8-flash) from the Lean proof and the goal states Lean reported at each step. Lean verified the proof; this explanation is a reading aid and is not itself machine-checked.
Lean source view module on GitHub
Choose a tactic — a marked line — to see the goals Lean had before and after it, as in Lean’s infoview. Step with ← → or j k.
open scoped Classicalopen SimpleGraph Finset Setlemma regular_bipartite_has_perfect_matching_card_le_card_biUnion {V : Type*} [Fintype V] [DecidableEq V] (G : SimpleGraph V) [DecidableRel G.Adj] {d : ℕ} (hd : 0 < d) (hreg : G.IsRegularOfDegree d) (S : Finset V) : #S ≤ #(S.biUnion (fun x => G.neighborFinset x)) := by let T := S.biUnion (fun x => G.neighborFinset x) have h_deg (v : V) : #(G.neighborFinset v) = d := by rw [card_neighborFinset_eq_degree] exact hreg v have h_above (u : V) (hu : u ∈ S) : #(bipartiteAbove G.Adj T u) = d := by have : bipartiteAbove G.Adj T u = G.neighborFinset u := by ext v simp only [bipartiteAbove, mem_filter, mem_neighborFinset] constructor · intro ⟨_, hadj⟩ exact hadj · intro hadj refine ⟨?_, hadj⟩ rw [Finset.mem_biUnion] exact ⟨u, hu, G.mem_neighborFinset u v |>.mpr hadj⟩ rw [this, h_deg] have h_below (v : V) : #(bipartiteBelow G.Adj S v) ≤ d := by have : bipartiteBelow G.Adj S v ⊆ G.neighborFinset v := by intro u hu simp only [bipartiteBelow, mem_filter] at hu simp only [mem_neighborFinset] exact hu.2.symm exact (Finset.card_le_card this).trans (h_deg v).le have h_sum_above : ∑ u ∈ S, #(bipartiteAbove G.Adj T u) = #S * d := by rw [sum_congr rfl h_above] simp have h_sum_below : ∑ v ∈ T, #(bipartiteBelow G.Adj S v) ≤ #T * d := by calc ∑ v ∈ T, #(bipartiteBelow G.Adj S v) _ ≤ ∑ v ∈ T, d := sum_le_sum fun v _ => h_below v _ = #T * d := by simp have h_eq := sum_card_bipartiteAbove_eq_sum_card_bipartiteBelow G.Adj (s := S) (t := T) have h_mul_le : #S * d ≤ #T * d := by rw [← h_sum_above, h_eq] exact h_sum_below exact Nat.le_of_mul_le_mul_right h_mul_le hdlemma regular_bipartite_has_perfect_matching_ncard_le_ncard_biUnion {V : Type*} [Fintype V] (G : SimpleGraph V) {d : ℕ} (hd : 0 < d) (hreg : G.IsRegularOfDegree d) (s : Set V) : s.ncard ≤ (⋃ x ∈ s, G.neighborSet x).ncard := by have h_eq : (⋃ x ∈ s, G.neighborSet x).toFinset = s.toFinset.biUnion (fun x => G.neighborFinset x) := by ext v simp rw [Set.ncard_eq_toFinset_card' s, Set.ncard_eq_toFinset_card' _, h_eq] exact regular_bipartite_has_perfect_matching_card_le_card_biUnion G hd hreg s.toFinset/-- Every d-regular bipartite graph with d > 0 has a perfect matching. -/theorem regular_bipartite_has_perfect_matching {V : Type*} [Fintype V] (G : SimpleGraph V) {d : ℕ} (hd : 0 < d) (hreg : G.IsRegularOfDegree d) (hbip : G.IsBipartite) : ∃ M : SimpleGraph.Subgraph G, M.IsPerfectMatching := by obtain ⟨p₁, p₂, hbipW⟩ := hbip.exists_isBipartiteWith exact exists_isPerfectMatching_of_forall_ncard_le hbipW (fun s => regular_bipartite_has_perfect_matching_ncard_le_ncard_biUnion G hd hreg s)