op_657_half_degree_packing_of_min_degree_le_two
For every squarefree natural number n with at least two distinct prime factors and any positive coprime integers a and b, 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_657_half_degree_packing_of_min_degree_le_two
(n : ℕ) (hn : Squarefree n) (hprimes : 2 ≤ n.primeFactors.card)
(a b : ℤ) (ha : 0 < a) (hb : 0 < b) (hcop : IsCoprime a 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, Coprime matchings of divisor sets
- Verified
- 29 Oct 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 4
- 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…
- 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…
- op_652_half_degree_packing_of_min_degree_le_twoFor 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…
- coprime_divisor_progression_graph_decidable_adjAdjacency in the coprime divisor progression graph coprime_divisor_progression_graph n a b is decidable via Classical.decRel.
Read back from the Lean
For every natural number $n$, assuming $n$ is squarefree and has at least 2 distinct prime factors, and for all integers $a$ and $b$ with $a > 0$, $b > 0$, and $\gcd(a, b) = 1$, consider the bipartite graph $G$ between the positive divisors of $n$ and the initial segment of the arithmetic progression $\{a + b \cdot t \mid 0 \le t < |\text{divisors}(n)|\}$, where an edge connects a divisor $d$ and a term $x$ if and only if $\gcd(d, x) = 1$. If the minimum degree of $G$ is at most 2, and there exists a perfect matching in $G$, then $G$ contains $\lfloor (\delta(G) + 1) / 2 \rfloor$ pairwise edge-disjoint perfect matchings (where $\delta(G)$ is the minimum vertex degree of $G$).
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
The theorem reduces immediately to an earlier result, op_652_half_degree_packing_of_min_degree_le_two, which proves the identical packing bound under the weaker hypothesis 2 ≤ n. The proof establishes 2 ≤ n by contradiction: if n < 2, then n would be 0 or 1, neither of which has any prime factors, contradicting the assumption that n has at least two distinct prime factors.
2 ≤ n
We proceed by contradiction: if n < 2, then n must be either 0 or 1. In both cases, n has no prime factors at all, so the number of prime factors is 0. This contradicts the hypothesis that n has at least 2 prime factors.
have hn2 : 2 ≤ n := by by_contra! hlt interval_cases n <;> simp at hprimes
The coprime divisor progression graph contains ⌈δ(B)/2⌉ pairwise edge-disjoint perfect matchings
With 2 ≤ n established, the theorem op_652_half_degree_packing_of_min_degree_le_two applies directly to yield the required number of edge-disjoint perfect matchings from the minimum degree bound and the existence of a perfect matching.
uses
op_652_half_degree_packing_of_min_degree_le_twoexact op_652_half_degree_packing_of_min_degree_le_two n hn2 a b hb hdeg hM
op_652_half_degree_packing_of_min_degree_le_two- For any integer n ≥ 2 and positive integer b, if the coprime divisor progression graph has minimum degree δ ≤ 2 and contains a perfect matching, then it contains at least ⌈δ/2⌉ pairwise edge-disjoint perfect matchings.
- The hypotheses that n is squarefree, that a > 0, and that a and b are coprime are not needed for the conclusion once n ≥ 2 is established, and are unused by the reduction.
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.
/-- If the coprime divisor progression graph for squarefree n has minimum degree at most 2 and has a perfect matching, it has at least ⌈δ/2⌉ edge-disjoint perfect matchings. -/theorem op_657_half_degree_packing_of_min_degree_le_two (n : ℕ) (hn : Squarefree n) (hprimes : 2 ≤ n.primeFactors.card) (a b : ℤ) (ha : 0 < a) (hb : 0 < b) (hcop : IsCoprime a 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 hn2 : 2 ≤ n := by by_contra! hlt interval_cases n <;> simp at hprimes exact op_652_half_degree_packing_of_min_degree_le_two n hn2 a b hb hdeg hM