digraph_cycle_packing_from_small_directed_cut
A nonempty directed block with at most two vertices in its outgoing boundary contains s disjoint directed cycles under the stated s-cycle hypothesis; an in-neighborhood cycle of a vertex outside both the block and boundary supplies one more.
Statement
theorem digraph_cycle_packing_from_small_directed_cut (α : Type) [Fintype α] [DecidableEq α] (D : Digraph α) [DecidableRel D.Adj] (r s : ℕ) (hdeg : ∀ v, r ≤ (Finset.univ.filter fun w => D.Adj v w).card) (hprev : ∀ T : Finset α, T.Nonempty → (∀ v ∈ T, r - 2 ≤ (T.filter fun w => D.Adj v w).card) → ∃ c : Fin s → Finset α, (∀ i, c i ⊆ T ∧ digraph_directed_cycle_on D (c i)) ∧ Pairwise (fun i j => Disjoint (c i) (c j))) (B S : Finset α) (hB : B.Nonempty) (hS : S.card ≤ 2) (hcut : ∀ b ∈ B, ∀ w, D.Adj b w → w ∈ B ∨ w ∈ S) (a : α) (haB : a ∉ B) (haS : a ∉ S) (C : Finset α) (hC : digraph_directed_cycle_on D C) (hin : ∀ v ∈ C, D.Adj v a) : ∃ c : Fin (s + 1) → Finset α, (∀ i, digraph_directed_cycle_on D (c i)) ∧ Pairwise (fun i j => Disjoint (c i) (c j))
- Source
- Generalized directed cut reduction for the minimum-counterexample route to OP-110.
- Verified
- 03 Nov 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 1
- digraph_directed_cycle_ons is the vertex set of a directed cycle of D: its vertices can be listed without repetition, at least two of them, each with an arc to the…
The proof, explained
The proof constructs a packing of s + 1 directed cycles by combining an existing cycle C with s cycles found inside the block B. Because every edge out of B lands in B ∪ S and |S| ≤ 2, every vertex in B retains at least r - 2 out-neighbors inside B, allowing the induction hypothesis to supply s pairwise disjoint cycles in B. Finally, the cycle C is shown to be disjoint from all cycles in B because its vertices all point to an external vertex a ∉ B ∪ S, completing the packing.
Every vertex b ∈ B has at least r - 2 out-neighbors in B.
For every vertex b ∈ B, any out-neighbor w of b must lie in B ∪ S by the cut condition `hcut`. Hence the full out-neighborhood N⁺(b) is a subset of (N⁺(b) ∩ B) ∪ S. Taking cardinalities, |N⁺(b)| ≤ |N⁺(b) ∩ B| + |S|. Since the total out-degree satisfies |N⁺(b)| ≥ r by the minimum degree hypothesis `hdeg` and |S| ≤ 2 by `hS`, linear arithmetic (`omega`) yields |N⁺(b) ∩ B| ≥ r - 2.
uses
Finset.mem_filter.mp,Finset.mem_filter.mpr,Finset.mem_union_left,Finset.mem_union_right,Finset.card_le_card,Finset.card_union_lehave hBdeg : ∀ b ∈ B, r - 2 ≤ (B.filter fun w => D.Adj b w).card := by intro b hb have hs : (Finset.univ.filter fun w => D.Adj b w) ⊆ (B.filter fun w => D.Adj b w) ∪ S := by intro w hw have hadj := (Finset.mem_filter.mp hw).2 rcases hcut b hb w hadj with hwB | hwS · exact Finset.mem_union_left _ (Finset.mem_filter.mpr ⟨hwB, hadj⟩) · exact Finset.mem_union_right _ hwS have hc := Finset.card_le_card hs have hu := Finset.card_union_le (B.filter fun w => D.Adj b w) S have hd := hdeg b omega
There exists a family of s pairwise disjoint directed cycles contained in B.
Applying the inductive hypothesis `hprev` to the nonempty subset B, which satisfies the internal degree bound |N⁺(b) ∩ B| ≥ r - 2 for all b ∈ B, provides s cycles t 0, ..., t (s - 1) contained in B that are pairwise disjoint.
obtain ⟨t, ht, hpair⟩ := hprev B hB hBdegThe cycle C is disjoint from every cycle t i in B.
Suppose for contradiction that some vertex x lies in C ∩ t i. Since t i ⊆ B, we have x ∈ B. Since x ∈ C, hypothesis `hin` ensures that (x, a) is an edge. By the cut hypothesis `hcut`, the out-neighbor a must lie in B or in S. But this contradicts the assumptions a ∉ B (`haB`) and a ∉ S (`haS`). Thus C and t i share no vertices.
uses
Finset.disjoint_left.mprhave hdis : ∀ i, Disjoint C (t i) := by intro i apply Finset.disjoint_left.mpr intro x hx hxt have hxB := (ht i).1 hxt rcases hcut x hxB a (hin x hx) with h | h · exact haB h · exact haS h
The extended family f on Fin (s + 1), defined by prepending C to the cycles t, consists of directed cycles.
We define f : Fin (s + 1) → Finset α by setting f(0) = C and f(i' + 1) = t(i') via `Fin.cases`. For index 0, f(0) = C is a directed cycle by hypothesis `hC`. For any successor index i' + 1, f(i' + 1) = t(i') is a directed cycle by property `ht` from the induction step.
uses
Fin.caseslet f : Fin (s + 1) → Finset α := Fin.cases C t refine ⟨f, ?_, ?_⟩ · intro i induction i using Fin.cases with | zero => exact hC | succ i' => exact (ht i').2
The s + 1 directed cycles in the family f are pairwise disjoint.
Given two distinct indices i ≠ j in Fin (s + 1), we inspect whether each index is 0 or a successor. If both are 0, this contradicts i ≠ j. If one is 0 and the other is a successor j' + 1, disjointness follows from C being disjoint from t(j') (`hdis`). If both are successors i' + 1 and j' + 1, then i' ≠ j', so f(i' + 1) = t(i') and f(j' + 1) = t(j') are disjoint by the pairwise disjointness `hpair` of the cycles in B.
uses
Fin.cases· intro i j hij induction i using Fin.cases with | zero => induction j using Fin.cases with | zero => exact (hij rfl).elim | succ j' => exact hdis j' | succ i' => induction j using Fin.cases with | zero => exact (hdis i').symm | succ j' => have hne : i' ≠ j' := by intro heq subst heq exact hij rfl exact hpair hne
Finset.mem_filter.mp- If x belongs to the filtered set {w ∈ s | p w}, then x ∈ s and p(x) holds.
Finset.mem_filter.mpr- If x ∈ s and p(x) holds, then x belongs to the filtered set {w ∈ s | p w}.
Finset.mem_union_left- An element of s belongs to the union s ∪ t.
Finset.mem_union_right- An element of t belongs to the union s ∪ t.
Finset.card_le_card- If a finite set s is a subset of t, then |s| ≤ |t|.
Finset.card_union_le- The cardinality of the union of two finite sets satisfies |s ∪ t| ≤ |s| + |t|.
Finset.disjoint_left.mpr- Two finite sets s and t are disjoint if no element of s belongs to t.
Fin.cases- Eliminator / case-analysis for Fin (n + 1): defines or proves a property by providing a value for 0 and values for successor indices.
- Linear arithmetic (`omega`) in step 1 automatically concludes the degree bound from the out-neighborhood inclusion and the cardinality bounds |S| ≤ 2 and deg(b) ≥ r.
- `Fin.cases` is Lean's case-analysis operator for the finite type Fin(s + 1), decomposing any index into either 0 or a successor i' + 1.
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.
theorem digraph_cycle_packing_from_small_directed_cut (α : Type) [Fintype α] [DecidableEq α] (D : Digraph α) [DecidableRel D.Adj] (r s : ℕ) (hdeg : ∀ v, r ≤ (Finset.univ.filter fun w => D.Adj v w).card) (hprev : ∀ T : Finset α, T.Nonempty → (∀ v ∈ T, r - 2 ≤ (T.filter fun w => D.Adj v w).card) → ∃ c : Fin s → Finset α, (∀ i, c i ⊆ T ∧ digraph_directed_cycle_on D (c i)) ∧ Pairwise (fun i j => Disjoint (c i) (c j))) (B S : Finset α) (hB : B.Nonempty) (hS : S.card ≤ 2) (hcut : ∀ b ∈ B, ∀ w, D.Adj b w → w ∈ B ∨ w ∈ S) (a : α) (haB : a ∉ B) (haS : a ∉ S) (C : Finset α) (hC : digraph_directed_cycle_on D C) (hin : ∀ v ∈ C, D.Adj v a) : ∃ c : Fin (s + 1) → Finset α, (∀ i, digraph_directed_cycle_on D (c i)) ∧ Pairwise (fun i j => Disjoint (c i) (c j)) := by have hBdeg : ∀ b ∈ B, r - 2 ≤ (B.filter fun w => D.Adj b w).card := by intro b hb have hs : (Finset.univ.filter fun w => D.Adj b w) ⊆ (B.filter fun w => D.Adj b w) ∪ S := by intro w hw have hadj := (Finset.mem_filter.mp hw).2 rcases hcut b hb w hadj with hwB | hwS · exact Finset.mem_union_left _ (Finset.mem_filter.mpr ⟨hwB, hadj⟩) · exact Finset.mem_union_right _ hwS have hc := Finset.card_le_card hs have hu := Finset.card_union_le (B.filter fun w => D.Adj b w) S have hd := hdeg b omega obtain ⟨t, ht, hpair⟩ := hprev B hB hBdeg have hdis : ∀ i, Disjoint C (t i) := by intro i apply Finset.disjoint_left.mpr intro x hx hxt have hxB := (ht i).1 hxt rcases hcut x hxB a (hin x hx) with h | h · exact haB h · exact haS h let f : Fin (s + 1) → Finset α := Fin.cases C t refine ⟨f, ?_, ?_⟩ · intro i induction i using Fin.cases with | zero => exact hC | succ i' => exact (ht i').2 · intro i j hij induction i using Fin.cases with | zero => induction j using Fin.cases with | zero => exact (hij rfl).elim | succ j' => exact hdis j' | succ i' => induction j using Fin.cases with | zero => exact (hdis i').symm | succ j' => have hne : i' ≠ j' := by intro heq subst heq exact hij rfl exact hpair hne