AFTD Auto-Formalizing Theoretical Domains

op_657_half_degree_packing_of_min_degree_le_two

theoremverified

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

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.

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

    lines 10–12

      have hn2 : 2 ≤ n := by
        by_contra! hlt
        interval_cases n <;> simp at hprimes
  2. 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.

    line 13

    uses op_652_half_degree_packing_of_min_degree_le_two

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

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

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