AFTD Auto-Formalizing Theoretical Domains

op_652_half_degree_packing_of_prime

theoremverified

For 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 ⌈δ(B)/2⌉ pairwise edge-disjoint perfect matchings.

Statement

theorem op_652_half_degree_packing_of_prime (p : ℕ) (hp : p.Prime) (a b : ℤ) (hb : 0 < b)
    (hM : ∃ M : (coprime_divisor_progression_graph p a b).Subgraph, M.IsPerfectMatching) :
    simple_graph_has_edge_disjoint_perfect_matchings
      (coprime_divisor_progression_graph p a b)
      (((coprime_divisor_progression_graph p a b).minDegree + 1) / 2)
Source
arXiv:2610.37512
Verified
29 Oct 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 4

Read back from the Lean

For any natural number p such that p is prime, and any integers a and b such that b > 0, if the coprime divisor progression graph G = coprime_divisor_progression_graph p a b contains at least one perfect matching (hM), then G contains at least ⌊(G.minDegree + 1) / 2⌋ 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

To prove that the coprime divisor progression graph B for a prime p contains at least ⌈δ(B)/2⌉ edge-disjoint perfect matchings, we first bound its minimum degree by 2. This is done by observing that the vertex 1 has neighbors only among the right-side vertices, whose total count is at most the number of divisors of p, which is 2 since p is prime. Finally, applying the previously established result for graphs with minimum degree at most 2 completes the proof.

  1. The minimum degree of the graph is bounded above by the degree of the vertex 1 on the left side

    Since p is prime and hence non-zero, 1 is a divisor of p. Picking the vertex v corresponding to 1, the minimum degree of the graph is at most the degree of v, which equals the number of neighbors of v. Therefore, it suffices to show that the neighborhood of v has cardinality at most 2.

    lines 7–13

    uses Nat.one_mem_divisors.mpr, minDegree_le_degree, le_trans

      have hdeg : (coprime_divisor_progression_graph p a b).minDegree ≤ 2 := by
        have h1_mem : 1 ∈ p.divisors := Nat.one_mem_divisors.mpr hp.ne_zero
        let v : {d // d ∈ p.divisors} ⊕ {x // x ∈ (Finset.range p.divisors.card).image (fun (t : ℕ) => a + b * (t : ℤ))} :=
          Sum.inl ⟨1, h1_mem⟩
        have hdeg_le := (coprime_divisor_progression_graph p a b).minDegree_le_degree v
        apply le_trans hdeg_le
        change ((coprime_divisor_progression_graph p a b).neighborFinset v).card ≤ 2
  2. All neighbors of v lie on the right side of the bipartite graph

    For any neighbor w of v, by definition of the neighbor set, v and w are adjacent. In the bipartite progression graph, no two left-side vertices can be adjacent (a neighbor on the left leads to False by definition of the graph). Thus w must be on the right side, meaning it belongs to the image under Sum.inr of the universal set of right-side vertices.

    lines 14–25

    uses mem_neighborFinset, Finset.mem_map, Finset.mem_univ

        have hsub : (coprime_divisor_progression_graph p a b).neighborFinset v ⊆
            Finset.map ⟨Sum.inr, Sum.inr_injective⟩ Finset.univ := by
          intro w hw
          rw [mem_neighborFinset] at hw
          cases w with
          | inl d' =>
            exfalso
            revert hw
            simp [coprime_divisor_progression_graph, fromRel]
          | inr x =>
            rw [Finset.mem_map]
            exact ⟨x, Finset.mem_univ _, rfl⟩
  3. The neighborhood of v has cardinality at most 2, so the minimum degree of the graph is at most 2

    Since the neighborhood of v is contained in the right-side vertices, its size is at most the size of the right vertex set. The right vertex set is the image of {0, ..., |divisors(p)| - 1} under an affine map, so its cardinality is at most the number of divisors of p. For a prime p, the divisors are exactly {1, p}, a set of size 2. By transitivity of inequality, the degree of v is at most 2, establishing that the graph has minimum degree at most 2.

    lines 26–33

    uses Finset.card_le_card, le_trans, Finset.card_map, Finset.card_univ, Fintype.card_coe, Finset.card_image_le, Finset.card_range, Nat.Prime.divisors, Finset.card_pair

        have hcard_le := Finset.card_le_card hsub
        apply le_trans hcard_le
        rw [Finset.card_map, Finset.card_univ, Fintype.card_coe]
        have himage_le := Finset.card_image_le (f := fun (t : ℕ) => a + b * (t : ℤ)) (s := Finset.range p.divisors.card)
        apply le_trans himage_le
        rw [Finset.card_range]
        rw [Nat.Prime.divisors hp]
        rw [Finset.card_pair hp.ne_one.symm]
  4. The graph contains at least ⌈δ/2⌉ pairwise edge-disjoint perfect matchings

    Since p is prime, p ≥ 2. With the minimum degree shown to be at most 2 and assuming the graph has a perfect matching, the existing theorem op_652_half_degree_packing_of_min_degree_le_two immediately yields the required number of edge-disjoint perfect matchings.

    line 34

    uses op_652_half_degree_packing_of_min_degree_le_two

      exact op_652_half_degree_packing_of_min_degree_le_two p hp.two_le a b hb hdeg hM
Nat.one_mem_divisors.mpr
1 divides any non-zero natural number
minDegree_le_degree
The minimum degree of a graph is at most the degree of any vertex
le_trans
Transitivity of inequality: if a ≤ b and b ≤ c, then a ≤ c
mem_neighborFinset
A vertex w is in the neighbor set of v if and only if v and w are adjacent
Finset.mem_map
An element is in the image under an embedding if and only if it is the image of some element
Finset.mem_univ
Every element belongs to the universal finset
Finset.card_le_card
A subset has cardinality at most that of the superset
Finset.card_map
Mapping a finset along an injective function preserves its cardinality
Finset.card_univ
The cardinality of the universal finset of a type is the cardinality of the type
Fintype.card_coe
The cardinality of a subtype as a finset equals the cardinality of the finset itself
Finset.card_image_le
The image of a finset under a function has cardinality at most that of the original finset
Finset.card_range
The range of n has cardinality n
Nat.Prime.divisors
The set of divisors of a prime p is {1, p}
Finset.card_pair
A set of two distinct elements has cardinality 2
op_652_half_degree_packing_of_min_degree_le_two
If the graph has minimum degree at most 2 and has a perfect matching, it has at least ⌈δ/2⌉ 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

/-- OP-652 holds for any prime p, as |D(p)| = 2 and ceil(delta/2) <= 1. -/theorem op_652_half_degree_packing_of_prime (p : ℕ) (hp : p.Prime) (a b : ℤ) (hb : 0 < b)    (hM : ∃ M : (coprime_divisor_progression_graph p a b).Subgraph, M.IsPerfectMatching) :    simple_graph_has_edge_disjoint_perfect_matchings      (coprime_divisor_progression_graph p a b)      (((coprime_divisor_progression_graph p a b).minDegree + 1) / 2) := open SimpleGraph in by  have hdeg : (coprime_divisor_progression_graph p a b).minDegree ≤ 2 := by    have h1_mem : 1 ∈ p.divisors := Nat.one_mem_divisors.mpr hp.ne_zero    let v : {d // d ∈ p.divisors} ⊕ {x // x ∈ (Finset.range p.divisors.card).image (fun (t : ℕ) => a + b * (t : ℤ))} :=      Sum.inl ⟨1, h1_mem⟩    have hdeg_le := (coprime_divisor_progression_graph p a b).minDegree_le_degree v    apply le_trans hdeg_le    change ((coprime_divisor_progression_graph p a b).neighborFinset v).card ≤ 2    have hsub : (coprime_divisor_progression_graph p a b).neighborFinset v ⊆        Finset.map ⟨Sum.inr, Sum.inr_injective⟩ Finset.univ := by      intro w hw      rw [mem_neighborFinset] at hw      cases w with      | inl d' =>        exfalso        revert hw        simp [coprime_divisor_progression_graph, fromRel]      | inr x =>        rw [Finset.mem_map]        exact ⟨x, Finset.mem_univ _, rfl⟩    have hcard_le := Finset.card_le_card hsub    apply le_trans hcard_le    rw [Finset.card_map, Finset.card_univ, Fintype.card_coe]    have himage_le := Finset.card_image_le (f := fun (t : ℕ) => a + b * (t : ℤ)) (s := Finset.range p.divisors.card)    apply le_trans himage_le    rw [Finset.card_range]    rw [Nat.Prime.divisors hp]    rw [Finset.card_pair hp.ne_one.symm]  exact op_652_half_degree_packing_of_min_degree_le_two p hp.two_le a b hb hdeg hM
See it in the graphDiscuss this resultChallenge it