op_652_half_degree_packing_of_prime
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
- 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…
- 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…
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.
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.
uses
Nat.one_mem_divisors.mpr,minDegree_le_degree,le_transhave 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
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.
uses
mem_neighborFinset,Finset.mem_map,Finset.mem_univhave 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⟩
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.
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_pairhave 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]
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.
uses
op_652_half_degree_packing_of_min_degree_le_twoexact 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
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 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