AFTD Auto-Formalizing Theoretical Domains

regular_bipartite_decompose_perfect_matchings

theoremverified

Every d-regular finite bipartite simple graph decomposes into d spanning one-regular subgraphs: every edge appears in exactly one of them.

Statement

theorem regular_bipartite_decompose_perfect_matchings {V : Type*} [Fintype V] (G : SimpleGraph V) (d : ℕ) (hreg : G.IsRegularOfDegree d) (hbip : G.IsBipartite) : ∃ F : Fin d → SimpleGraph V, (∀ i, (F i).IsRegularOfDegree 1 ∧ F i ≤ G) ∧ ∀ u v, G.Adj u v ↔ ∃! i, (F i).Adj u v
Source
Regular bipartite graph decomposition used in arXiv:2609.35280, Section 3.1, from repeated perfect matching removal.
Verified
14 Nov 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 3

The proof, explained

The theorem is proved by induction on the degree $d$. When $d = 0$, $G$ has no edges and the empty family of subgraphs vacuously decomposes $G$. For the induction step $d + 1$, Hall's Marriage Theorem produces a perfect matching, which forms a 1-regular spanning subgraph $P$. Removing $P$ from $G$ leaves a $d$-regular bipartite graph $R = G \setminus P$, to which the induction hypothesis applies. Prepending $P$ to the $d$ matchings decomposing $R$ yields the desired decomposition of $G$ into $d + 1$ one-regular spanning subgraphs.

  1. The base case $d = 0$ holds: the empty family of subgraphs decomposes any 0-regular graph.

    We proceed by induction on $d$. When $d = 0$, every vertex of $G$ has degree 0, so $G$ has no edges. We define the family of subgraphs to be empty, indexed by `Fin 0` via `Fin.elim0`. The condition that each subgraph is 1-regular and contained in $G$ holds vacuously. For any pair of vertices $u, v$, an edge in $G$ would force $G$'s degree at $u$ to be strictly positive, contradicting 0-regularity; similarly, no edge exists in the empty family. Hence both sides of the equivalence are false.

    lines 5–18

    uses Fin.elim0

      classical
      induction d generalizing G with
      | zero =>
        refine ⟨Fin.elim0, ?_, ?_⟩
        · intro i
          exact Fin.elim0 i
        · intro u v
          constructor
          · intro huv
            have hpos : 0 < G.degree u := (G.degree_pos_iff_exists_adj u).2 ⟨v, huv⟩
            have hz : G.degree u = 0 := hreg u
            omega
          · rintro ⟨i, _, _⟩
            exact Fin.elim0 i
  2. The graph $G$ contains a 1-regular spanning subgraph $P$ corresponding to a perfect matching.

    In the inductive step for degree $d + 1$, since $d + 1 > 0$ by `Nat.succ_pos`, Hall's Marriage Theorem (via `regular_bipartite_has_perfect_matching`) guarantees that the $(d+1)$-regular bipartite graph $G$ has a perfect matching $M$. We let $P$ be the spanning subgraph formed by the edges of $M$, and $R = G \setminus P$ be the remainder graph. By construction $P \le G$, and because every vertex has degree 1 in a perfect matching, $P$ is 1-regular.

    lines 19–29

    uses regular_bipartite_has_perfect_matching, Nat.succ_pos

      | succ d ih =>
        obtain ⟨M, hM⟩ := regular_bipartite_has_perfect_matching G (Nat.succ_pos d) hreg hbip
        let P : SimpleGraph V := M.spanningCoe
        let R : SimpleGraph V := G \ P
        letI : DecidableRel R.Adj := Classical.decRel R.Adj
        have hp_le : P ≤ G := M.spanningCoe_le
        have hp_reg : P.IsRegularOfDegree 1 := by
          intro v
          change M.spanningCoe.degree v = 1
          rw [M.degree_spanningCoe]
          exact (Subgraph.isPerfectMatching_iff_forall_degree.mp hM) v
  3. The remainder graph $R = G \setminus P$ is a $d$-regular bipartite graph.

    Because $R = G \setminus P \le G$ by `sdiff_le`, $R$ inherits 2-colorability from $G$ (`Colorable.mono_left`), so $R$ is bipartite. For any vertex $v$, its neighborhood in $P$ is a subset of its neighborhood in $G$, with $|N_G(v)| = d + 1$ (by `card_neighborFinset_eq_degree` and regularity of $G$) and $|N_P(v)| = 1$ (by regularity of $P$). By `neighborFinset_sdiff` and `Finset.card_sdiff_of_subset`, the neighborhood of $v$ in $R$ has size $(d + 1) - 1 = d$, so $R$ is $d$-regular.

    lines 30–46

    uses sdiff_le, Colorable.mono_left, card_neighborFinset_eq_degree, neighborFinset_sdiff, Finset.card_sdiff_of_subset

        have hr_le : R ≤ G := sdiff_le
        have hr_bip : R.IsBipartite := Colorable.mono_left hr_le hbip
        have hr_reg : R.IsRegularOfDegree d := by
          intro v
          have hs : P.neighborFinset v ⊆ G.neighborFinset v := by
            intro w hw
            exact (G.mem_neighborFinset v w).mpr (hp_le ((P.mem_neighborFinset v w).mp hw))
          have hgc : (G.neighborFinset v).card = d + 1 := by
            rw [card_neighborFinset_eq_degree]
            exact hreg v
          have hpc : (P.neighborFinset v).card = 1 := by
            rw [card_neighborFinset_eq_degree]
            exact hp_reg v
          change (G \ P).degree v = d
          rw [← card_neighborFinset_eq_degree,
              neighborFinset_sdiff, Finset.card_sdiff_of_subset hs, hgc, hpc]
          omega
  4. Prepending $P$ to the $d$ matchings from the induction hypothesis yields a family $F'$ of $d + 1$ subgraphs that are each 1-regular and contained in $G$.

    By the induction hypothesis applied to $R$, there is a family $F$ of $d$ 1-regular subgraphs that decompose $R$. Using `Fin.cons`, we form $F'$ on `Fin (d + 1)` by setting $F'(0) = P$ and $F'(j + 1) = F(j)$. By case analysis on `Fin (d + 1)` using `Fin.cases`: $F'(0) = P$ is 1-regular and $P \le G$; for any successor index $j + 1$, $F(j)$ is 1-regular by the induction hypothesis, and $F(j) \le R \le G$ by transitivity.

    lines 47–59

    uses Fin.cons, Fin.cases

        obtain ⟨F, hFreg, hFedges⟩ := ih R hr_reg hr_bip
        let F' : Fin (d+1) → SimpleGraph V := Fin.cons P F
        have hFzero : F' 0 = P := by simp [F']
        have hFsucc (i : Fin d) : F' i.succ = F i := by simp [F']
        refine ⟨F', ?_, ?_⟩
        · intro i
          induction i using Fin.cases with
          | zero =>
            change P.IsRegularOfDegree 1 ∧ P ≤ G
            exact ⟨hp_reg, hp_le⟩
          | succ j =>
            rw [hFsucc]
            exact ⟨(hFreg j).1, (hFreg j).2.trans hr_le⟩
  5. Every edge of $G$ belongs to a unique subgraph in the family $F'$.

    Let $uv$ be an edge of $G$. We split on whether $uv$ belongs to $P$. If $uv \in P$, it belongs to $F'(0)$; it cannot belong to any successor index $j + 1$, because that would imply $uv \in F(j) \le R = G \setminus P$, contradicting `sdiff_adj` and yielding `False.elim`. If $uv \notin P$, then $uv$ belongs to $R = G \setminus P$ by `sdiff_adj`. The induction hypothesis gives a unique $j \in \text{Fin } d$ such that $uv \in F(j)$, placing $uv$ in $F'(j + 1)$. This edge cannot be in $F'(0) = P$, and by uniqueness of $j$ in $R$, it cannot appear at any other successor index, using `congrArg` on `Fin.succ`.

    lines 60–85

    uses sdiff_adj, False.elim, Fin.cases, congrArg

        · intro u v
          constructor
          · intro huv
            by_cases hpuv : P.Adj u v
            · refine ⟨0, ?_, ?_⟩
              · simpa [hFzero] using hpuv
              · intro i hi
                induction i using Fin.cases with
                | zero => rfl
                | succ j =>
                  rw [hFsucc] at hi
                  have hr : R.Adj u v := (hFreg j).2 hi
                  have hn : ¬ P.Adj u v := (sdiff_adj G P u v).mp hr |>.2
                  exact False.elim (hn hpuv)
            · have hr : R.Adj u v := (sdiff_adj G P u v).mpr ⟨huv, hpuv⟩
              obtain ⟨j, hj, hjuniq⟩ := (hFedges u v).mp hr
              refine ⟨j.succ, ?_, ?_⟩
              · simpa [hFsucc] using hj
              · intro i hi
                induction i using Fin.cases with
                | zero =>
                  have : P.Adj u v := by simpa [hFzero] using hi
                  exact False.elim (hpuv this)
                | succ k =>
                  rw [hFsucc] at hi
                  exact congrArg Fin.succ (hjuniq k hi)
  6. Every edge in any subgraph of the family $F'$ is an edge of $G$.

    Conversely, suppose $uv$ is an edge of $F'(i)$ for some $i \in \text{Fin } (d + 1)$. Using `Fin.cases`, if $i = 0$, then $uv \in P \le G$. If $i = j + 1$, then $uv \in F(j) \le R \le G$. In either case $uv$ is an edge of $G$, completing the proof of the equivalence and the induction step.

    lines 86–93

    uses Fin.cases

          · rintro ⟨i, hi, _⟩
            induction i using Fin.cases with
            | zero =>
              rw [hFzero] at hi
              exact hp_le hi
            | succ j =>
              rw [hFsucc] at hi
              exact hr_le ((hFreg j).2 hi)
Fin.elim0
The principle of explosion for the empty type `Fin 0`: from an element of `Fin 0`, any goal follows.
regular_bipartite_has_perfect_matching
Every $d$-regular bipartite finite graph with $d > 0$ contains a perfect matching.
Nat.succ_pos
The successor of any natural number is strictly positive ($0 < d + 1$).
sdiff_le
Set difference is bounded by the original set ($A \setminus B \le A$).
Colorable.mono_left
A subgraph of an $n$-colorable graph is $n$-colorable; in particular, a subgraph of a bipartite graph is bipartite.
card_neighborFinset_eq_degree
The number of neighbors in the neighbor finset of a vertex equals its degree in the graph.
neighborFinset_sdiff
The neighbor finset of a vertex in the difference graph $G_1 \setminus G_2$ is the set difference of its neighbor finsets in $G_1$ and $G_2$.
Finset.card_sdiff_of_subset
If $s \subseteq t$, then $|t \setminus s| = |t| - |s|$ for finite sets.
Fin.cons
Constructs a function on `Fin (n + 1)` by specifying the value at 0 and a function on the remaining $n$ elements.
Fin.cases
Case analysis on `Fin (n + 1)`: every element is either 0 or the successor of an element of `Fin n`.
sdiff_adj
Two vertices are adjacent in $G_1 \setminus G_2$ if and only if they are adjacent in $G_1$ and not adjacent in $G_2$.
False.elim
From a contradiction (`False`), any proposition can be derived.
congrArg
If two arguments are equal, applying the same function to both yields equal values ($a = b \implies f(a) = f(b)$).

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 SimpleGraph Finsetopen scoped Classicaltheorem regular_bipartite_decompose_perfect_matchings {V : Type*} [Fintype V] (G : SimpleGraph V) (d : ℕ) (hreg : G.IsRegularOfDegree d) (hbip : G.IsBipartite) : ∃ F : Fin d → SimpleGraph V, (∀ i, (F i).IsRegularOfDegree 1 ∧ F i ≤ G) ∧ ∀ u v, G.Adj u v ↔ ∃! i, (F i).Adj u v := by  classical  induction d generalizing G with  | zero =>    refine ⟨Fin.elim0, ?_, ?_⟩    · intro i      exact Fin.elim0 i    · intro u v      constructor      · intro huv        have hpos : 0 < G.degree u := (G.degree_pos_iff_exists_adj u).2 ⟨v, huv⟩        have hz : G.degree u = 0 := hreg u        omega      · rintro ⟨i, _, _⟩        exact Fin.elim0 i  | succ d ih =>    obtain ⟨M, hM⟩ := regular_bipartite_has_perfect_matching G (Nat.succ_pos d) hreg hbip    let P : SimpleGraph V := M.spanningCoe    let R : SimpleGraph V := G \ P    letI : DecidableRel R.Adj := Classical.decRel R.Adj    have hp_le : P ≤ G := M.spanningCoe_le    have hp_reg : P.IsRegularOfDegree 1 := by      intro v      change M.spanningCoe.degree v = 1      rw [M.degree_spanningCoe]      exact (Subgraph.isPerfectMatching_iff_forall_degree.mp hM) v    have hr_le : R ≤ G := sdiff_le    have hr_bip : R.IsBipartite := Colorable.mono_left hr_le hbip    have hr_reg : R.IsRegularOfDegree d := by      intro v      have hs : P.neighborFinset v ⊆ G.neighborFinset v := by        intro w hw        exact (G.mem_neighborFinset v w).mpr (hp_le ((P.mem_neighborFinset v w).mp hw))      have hgc : (G.neighborFinset v).card = d + 1 := by        rw [card_neighborFinset_eq_degree]        exact hreg v      have hpc : (P.neighborFinset v).card = 1 := by        rw [card_neighborFinset_eq_degree]        exact hp_reg v      change (G \ P).degree v = d      rw [← card_neighborFinset_eq_degree,          neighborFinset_sdiff, Finset.card_sdiff_of_subset hs, hgc, hpc]      omega    obtain ⟨F, hFreg, hFedges⟩ := ih R hr_reg hr_bip    let F' : Fin (d+1) → SimpleGraph V := Fin.cons P F    have hFzero : F' 0 = P := by simp [F']    have hFsucc (i : Fin d) : F' i.succ = F i := by simp [F']    refine ⟨F', ?_, ?_⟩    · intro i      induction i using Fin.cases with      | zero =>        change P.IsRegularOfDegree 1 ∧ P ≤ G        exact ⟨hp_reg, hp_le⟩      | succ j =>        rw [hFsucc]        exact ⟨(hFreg j).1, (hFreg j).2.trans hr_le⟩    · intro u v      constructor      · intro huv        by_cases hpuv : P.Adj u v        · refine ⟨0, ?_, ?_⟩          · simpa [hFzero] using hpuv          · intro i hi            induction i using Fin.cases with            | zero => rfl            | succ j =>              rw [hFsucc] at hi              have hr : R.Adj u v := (hFreg j).2 hi              have hn : ¬ P.Adj u v := (sdiff_adj G P u v).mp hr |>.2              exact False.elim (hn hpuv)        · have hr : R.Adj u v := (sdiff_adj G P u v).mpr ⟨huv, hpuv⟩          obtain ⟨j, hj, hjuniq⟩ := (hFedges u v).mp hr          refine ⟨j.succ, ?_, ?_⟩          · simpa [hFsucc] using hj          · intro i hi            induction i using Fin.cases with            | zero =>              have : P.Adj u v := by simpa [hFzero] using hi              exact False.elim (hpuv this)            | succ k =>              rw [hFsucc] at hi              exact congrArg Fin.succ (hjuniq k hi)      · rintro ⟨i, hi, _⟩        induction i using Fin.cases with        | zero =>          rw [hFzero] at hi          exact hp_le hi        | succ j =>          rw [hFsucc] at hi          exact hr_le ((hFreg j).2 hi)
See it in the graphDiscuss this resultChallenge it