regular_bipartite_decompose_perfect_matchings
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
- regular_bipartite_has_perfect_matchingEvery d-regular bipartite simple graph on a finite vertex set, with degree d > 0, has a perfect matching.
- uniquely_k4_saturated_max_degree_six_order_twelveThere exists a simple graph G on Fin 12 such that G is uniquely K_4-saturated and the maximum degree of G equals 6.
- OrderAn order of dimension d is a permutation of the attribute set {0, ..., d-1}, represented as a list without duplicates containing all…
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.
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.
uses
Fin.elim0classical 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
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.
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) vThe 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.
uses
sdiff_le,Colorable.mono_left,card_neighborFinset_eq_degree,neighborFinset_sdiff,Finset.card_sdiff_of_subsethave 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
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.
uses
Fin.cons,Fin.casesobtain ⟨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⟩
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`.
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)
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.
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)$).
- Lean's `omega` tactic is used to handle basic integer arithmetic on degrees, specifically showing that 0-regularity contradicts having an edge in the base case, and that $(d + 1) - 1 = d$ in the inductive step.
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 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)