AFTD Auto-Formalizing Theoretical Domains

regular_bipartite_has_perfect_matching

theoremverifiedformalization

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

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.

  1. 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.

    lines 8–11

    uses card_neighborFinset_eq_degree

      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
  2. 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.

    lines 12–23

    uses Finset.mem_biUnion

      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]
  3. 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.

    lines 24–30

    uses Finset.card_le_card

      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
  4. 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.

    lines 31–33

    uses sum_congr

      have h_sum_above : ∑ u ∈ S, #(bipartiteAbove G.Adj T u) = #S * d := by
        rw [sum_congr rfl h_above]
        simp
  5. 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.

    lines 34–37

    uses sum_le_sum

      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
  6. 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|.

    lines 38–42

    uses sum_card_bipartiteAbove_eq_sum_card_bipartiteBelow, Nat.le_of_mul_le_mul_right

      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 hd
  7. 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`.

    lines 48–52

    uses Set.ncard_eq_toFinset_card', regular_bipartite_has_perfect_matching_card_le_card_biUnion

      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
  8. 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`.

    lines 59–61

    uses exists_isPerfectMatching_of_forall_ncard_le, regular_bipartite_has_perfect_matching_ncard_le_ncard_biUnion

      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)
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)|.

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

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)
See it in the graphDiscuss this resultChallenge it