AFTD Auto-Formalizing Theoretical Domains

op_652_half_degree_packing_of_min_degree_le_two

theoremverified

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
Used by 2

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

  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.

    lines 8–10

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

    lines 11–13

    uses Fin.elim0

      · rw [h0]
        use fun i => Fin.elim0 i
        refine ⟨fun i => Fin.elim0 i, fun i => Fin.elim0 i⟩
  3. 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$.

    lines 14–17

    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.

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

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