op_652_half_degree_packing_of_min_degree_le_two
For any natural number n ≥ 2 and integers a, b with b > 0, if the coprime divisor progression graph B has minimum degree at most 2 and contains a perfect matching, then B contains at least ⌈δ(B)/2⌉ pairwise edge-disjoint perfect matchings.
Statement
theorem op_652_half_degree_packing_of_min_degree_le_two (n : ℕ) (hn : 2 ≤ n) (a b : ℤ) (hb : 0 < b)
(hdeg : (coprime_divisor_progression_graph n a b).minDegree ≤ 2)
(hM : ∃ M : (coprime_divisor_progression_graph n a b).Subgraph, M.IsPerfectMatching) :
simple_graph_has_edge_disjoint_perfect_matchings
(coprime_divisor_progression_graph n a b)
(((coprime_divisor_progression_graph n a b).minDegree + 1) / 2)- Source
- arXiv:2610.37512
- Verified
- 29 Oct 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 3
- coprime_divisor_progression_graphFor a natural number n and integers a and b, the coprime divisor progression graph is the bipartite simple graph on the disjoint union of…
- coprime_divisor_progression_graph_decidable_adjAdjacency in the coprime divisor progression graph coprime_divisor_progression_graph n a b is decidable via Classical.decRel.
- simple_graph_has_edge_disjoint_perfect_matchingsA simple graph G has at least k pairwise edge-disjoint perfect matchings if there exists an indexed family of k subgraphs of G, each of…
- Used by 2
- op_657_half_degree_packing_of_min_degree_le_twoFor every squarefree natural number n with at least two distinct prime factors and any positive coprime integers a and b, if the coprime…
- op_652_half_degree_packing_of_primeFor any prime p and integers a, b with b > 0, if the coprime divisor progression graph B has a perfect matching, then B contains at least…
Read back from the Lean
For any natural number $n \ge 2$ and integers $a, b$ with $b > 0$, consider the bipartite graph $G = \text{coprime\_divisor\_progression\_graph}(n, a, b)$ whose parts are the divisors of $n$ and the arithmetic progression $\{a + b \cdot t \mid 0 \le t < \tau(n)\}$ (where $\tau(n)$ is the number of divisors of $n$), with an edge between a divisor $d$ and a progression element $x$ if and only if $\gcd(d, x) = 1$. If the minimum degree $\delta(G)$ of this graph is at most $2$, and if $G$ has at least one perfect matching, then $G$ has $\lfloor (\delta(G) + 1) / 2 \rfloor$ pairwise edge-disjoint perfect matchings.
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
Because the minimum degree $\delta(B)$ is at most $2$, the target quantity $\lceil \delta(B)/2 \rceil = \lfloor (\delta(B)+1)/2 \rfloor$ can only be $0$ or $1$. If the target is $0$, the requirement is vacuously satisfied by an empty family of matchings. If the target is $1$, the single perfect matching guaranteed by assumption suffices, as pairwise disjointness holds vacuously for an index set of size $1$.
The target number of matchings, $\lfloor (\delta(B) + 1)/2 \rfloor$, is either $0$ or $1$, reducing the goal to these two cases.
Since the minimum degree $\delta(B)$ satisfies $\delta(B) \le 2$ and is non-negative, integer division ensures that $(\delta(B) + 1)/2$ is either $0$ or $1$. The linear arithmetic tactic `omega` verifies this disjunction, and `rcases` splits the proof into the two corresponding cases.
have hd : ((coprime_divisor_progression_graph n a b).minDegree + 1) / 2 = 0 ∨ ((coprime_divisor_progression_graph n a b).minDegree + 1) / 2 = 1 := by omega rcases hd with h0 | h1
When $\lfloor (\delta(B) + 1) / 2 \rfloor = 0$, the graph vacuously contains $0$ edge-disjoint perfect matchings.
Substituting $0$ for the target number of matchings, the goal is to produce an empty family of matchings indexed by $\text{Fin } 0$. Using `Fin.elim0`, we construct the empty family. Both requirements—that each matching is perfect and that distinct matchings are pairwise edge-disjoint—hold vacuously because the index type $\text{Fin } 0$ is uninhabited.
uses
Fin.elim0· rw [h0] use fun i => Fin.elim0 i refine ⟨fun i => Fin.elim0 i, fun i => Fin.elim0 i⟩
When $\lfloor (\delta(B) + 1) / 2 \rfloor = 1$, the assumed perfect matching provides the single required matching.
Substituting $1$ for the target number of matchings, we extract the perfect matching $M$ from the existence hypothesis and define the constant family indexed by $\text{Fin } 1$ returning $M$. The family consists of a perfect matching by construction, and pairwise edge-disjointness is vacuous: `Fin 1` is a subsingleton, so any two indices $i, j \in \text{Fin } 1$ are equal by `Subsingleton.elim`, which contradicts the distinctness assumption $i \neq j$.
uses
Subsingleton.elim· rw [h1] obtain ⟨M, hM⟩ := hM use fun _ => M refine ⟨fun _ => hM, fun i j hij => (hij (Subsingleton.elim i j)).elim⟩
Fin.elim0- The elimination principle for the empty type `Fin 0`: an element of `Fin 0` yields a term of any type.
Subsingleton.elim- Any two elements of a subsingleton type (a type with at most one term, such as `Fin 1`) are equal.
- The ceiling $\lceil \delta(B)/2 \rceil$ is represented in natural number arithmetic as `(minDegree + 1) / 2`.
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.
/-- OP-652 holds when the minimum degree of B is at most 2, since ceil(delta/2) <= 1. -/theorem op_652_half_degree_packing_of_min_degree_le_two (n : ℕ) (hn : 2 ≤ n) (a b : ℤ) (hb : 0 < b) (hdeg : (coprime_divisor_progression_graph n a b).minDegree ≤ 2) (hM : ∃ M : (coprime_divisor_progression_graph n a b).Subgraph, M.IsPerfectMatching) : simple_graph_has_edge_disjoint_perfect_matchings (coprime_divisor_progression_graph n a b) (((coprime_divisor_progression_graph n a b).minDegree + 1) / 2) := by have hd : ((coprime_divisor_progression_graph n a b).minDegree + 1) / 2 = 0 ∨ ((coprime_divisor_progression_graph n a b).minDegree + 1) / 2 = 1 := by omega rcases hd with h0 | h1 · rw [h0] use fun i => Fin.elim0 i refine ⟨fun i => Fin.elim0 i, fun i => Fin.elim0 i⟩ · rw [h1] obtain ⟨M, hM⟩ := hM use fun _ => M refine ⟨fun _ => hM, fun i j hij => (hij (Subsingleton.elim i j)).elim⟩