digraph_clean_outneighborhood_cycle_packing_step
A directed cycle inside a clean out-neighborhood can be added to any k-cycle packing theorem two outdegree units lower.
Statement
theorem digraph_clean_outneighborhood_cycle_packing_step (α : Type) [Fintype α] [DecidableEq α] (D : Digraph α) [DecidableRel D.Adj] (k d : ℕ) (hloop : ∀ v, ¬ D.Adj v v) (hori : ∀ u v, D.Adj u v → ¬ D.Adj v u) (hdeg : ∀ v, d + 2 ≤ (Finset.univ.filter fun w => D.Adj v w).card) (hpack : ∀ T : Finset α, T.Nonempty → (∀ v ∈ T, d ≤ (T.filter fun w => D.Adj v w).card) → ∃ s : Fin k → Finset α, (∀ i, s i ⊆ T ∧ digraph_directed_cycle_on D (s i)) ∧ Pairwise (fun i j => Disjoint (s i) (s j))) (v : α) (C : Finset α) (hC : digraph_directed_cycle_on D C) (hCout : ∀ w ∈ C, D.Adj v w) (hclean : ∀ a b, a ≠ b → D.Adj v a → D.Adj v b → ∀ x, D.Adj x a → D.Adj x b → x = v) (p : α) (hpv : D.Adj p v) : ∃ s : Fin (k + 1) → Finset α, (∀ i, digraph_directed_cycle_on D (s i)) ∧ Pairwise (fun i j => Disjoint (s i) (s j))
- Source
- General linear out-neighborhood deletion step for OP-110 and the corresponding k-cycle problem.
- 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…
- Used by 4
- digraph_linear_arc_dominated_cycle_packing_stepThe k-cycle theorem at outdegree d implies the (k+1)-cycle theorem at outdegree d+2 for oriented linear arc-dominated digraphs.
- digraph_trianglefree_weighted_overlap_cycle_packing_stepFor a loopless oriented arc-dominated digraph of directed girth at least four, the k-cycle theorem at outdegree d implies a (k+1)-cycle…
- digraph_small_overlap_arc_dominated_cycle_packing_stepThe k-cycle theorem at outdegree d implies the (k+1)-cycle theorem for oriented arc-dominated digraphs of minimum outdegree at least d+2…
- digraph_girth_weighted_overlap_cycle_packing_stepFor a loopless oriented arc-dominated digraph of directed girth at least g, the k-cycle theorem at outdegree d implies a (k+1)-cycle…
The proof, explained
To construct k + 1 pairwise disjoint directed cycles, we remove vertex v and the given cycle C from the vertex set to form T = (V \ {v}) \ C. The in-neighbor p of v cannot equal v (no self-loops) nor belong to C (by orientation), ensuring T is nonempty. By the cleanliness condition, any vertex x ∈ T has at most one out-neighbor in C, so at most two of its out-neighbors (one in C and possibly v) lie outside T; since x has total out-degree at least d + 2, its out-degree restricted to T is at least d. Applying the lower-degree packing hypothesis to T yields k pairwise disjoint directed cycles in T, which are all disjoint from C by construction, providing the desired (k + 1)-cycle packing.
The vertex set T = (V \ {v}) \ C is nonempty, witnessed by the in-neighbor p of v.
We define T by removing the vertex v and all vertices of the directed cycle C from the graph. The in-neighbor p of v cannot equal v because D has no self-loops (hloop). Nor can p belong to C: every vertex in C is an out-neighbor of v (hCout), so if p were in C, we would have both p → v and v → p, contradicting the orientation assumption (hori). Hence p ∈ T, which proves T is nonempty.
classical let T : Finset α := (Finset.univ.erase v) \ C have hpne : p ≠ v := by intro h; subst p; exact hloop v hpv have hpC : p ∉ C := by intro hp exact (hori p v hpv) (hCout p hp) have hT : T.Nonempty := by refine ⟨p, ?_⟩ simp [T, hpne, hpC]
For every vertex x ∈ T, at most one out-neighbor of x lies in C.
Let x ∈ T, so x ≠ v. Let A = N⁺(x) ∩ C be the set of out-neighbors of x in C. If A contained two distinct vertices a and b, then both a and b would be out-neighbors of v (since C ⊆ N⁺(v)) and out-neighbors of x. By the cleanliness hypothesis (hclean), any vertex with directed edges to two distinct out-neighbors of v must be v itself, which would imply x = v, a contradiction. Thus, |A| ≤ 1 by Finset.card_le_one.mpr.
uses
Finset.mem_sdiff.mp,Finset.mem_erase.mp,Finset.card_le_one.mpr,Finset.mem_filter.mphave hTdeg : ∀ x ∈ T, d ≤ (T.filter fun w => D.Adj x w).card := by intro x hx have hxne : x ≠ v := by have := (Finset.mem_sdiff.mp hx).1 exact (Finset.mem_erase.mp this).1 let A : Finset α := C.filter fun w => D.Adj x w have hA : A.card ≤ 1 := by apply Finset.card_le_one.mpr intro a ha b hb have haC : a ∈ C := (Finset.mem_filter.mp ha).1 have hbC : b ∈ C := (Finset.mem_filter.mp hb).1 have hxa : D.Adj x a := (Finset.mem_filter.mp ha).2 have hxb : D.Adj x b := (Finset.mem_filter.mp hb).2 by_contra hab exact hxne (hclean a b hab (hCout a haC) (hCout b hbC) x hxa hxb)
Every vertex x ∈ T has out-degree at least d in the induced sub-digraph on T.
Any out-neighbor w of x must either be v, belong to C (and thus to A = N⁺(x) ∩ C), or belong to T. Consequently, the total out-neighborhood N⁺(x) is a subset of (N⁺(x) ∩ T) ∪ (A ∪ {v}). Since |A| ≤ 1 and |{v}| = 1, the set A ∪ {v} has size at most 2. Because the total out-degree of x is at least d + 2 (hdeg), linear arithmetic (omega) shows that |N⁺(x) ∩ T| ≥ d.
uses
Finset.mem_filter.mp,Finset.mem_filter.mpr,Finset.mem_union_right,Finset.mem_union_left,Finset.card_le_card,Finset.card_union_le,Finset.card_singletonhave hs : (Finset.univ.filter fun w => D.Adj x w) ⊆ (T.filter fun w => D.Adj x w) ∪ (A ∪ {v}) := by intro w hw have hwadj := (Finset.mem_filter.mp hw).2 by_cases hwv : w = v · simp [hwv] by_cases hwC : w ∈ C · have hwA : w ∈ A := Finset.mem_filter.mpr ⟨hwC, hwadj⟩ exact Finset.mem_union_right _ (Finset.mem_union_left _ hwA) · have hwT : w ∈ T := by simp [T, hwv, hwC] exact Finset.mem_union_left _ (Finset.mem_filter.mpr ⟨hwT, hwadj⟩) have hsub := Finset.card_le_card hs have hunion := Finset.card_union_le (T.filter fun w => D.Adj x w) (A ∪ {v}) have hsmall := Finset.card_union_le A ({v} : Finset α) have hd := hdeg x simp only [Finset.card_singleton] at hsmall omega
There exist k pairwise disjoint directed cycles in T, each disjoint from C.
Since T is nonempty and every vertex in T has out-degree at least d into T, the inductive cycle packing hypothesis (hpack) provides a family of k pairwise disjoint directed cycles t₀, ..., t_{k-1} contained in T. Because each t_i ⊆ T and T is disjoint from C by construction, every t_i is disjoint from C.
uses
Finset.disjoint_left.mpr,Finset.mem_sdiff.mpobtain ⟨t, ht, hpair⟩ := hpack T hT hTdeg have hdis : ∀ i, Disjoint C (t i) := by intro i apply Finset.disjoint_left.mpr intro x hx hxt have hxT := (ht i).1 hxt exact (Finset.mem_sdiff.mp hxT).2 hx
Combining C with the k cycles from T yields k + 1 pairwise disjoint directed cycles in D.
We define the family f on Fin (k + 1) by setting f(0) = C and f(i + 1) = t_i using Fin.cases. Each f(i) is a directed cycle: f(0) = C is a cycle by assumption (hC), and each f(i + 1) = t_i is a cycle from the packing in T. Disjointness between any two distinct cycles f(i) and f(j) holds because C is disjoint from each t_m and the cycles t_m are pairwise disjoint among themselves.
uses
Fin.caseslet f : Fin (k + 1) → Finset α := Fin.cases C t refine ⟨f, ?_, ?_⟩ · intro i refine Fin.cases ?_ (fun i => ?_) i · exact hC · exact (ht i).2 · intro i refine Fin.cases ?_ (fun i => ?_) i · intro j refine Fin.cases ?_ (fun j => ?_) j · intro hij exact (hij rfl).elim · intro _ exact hdis j · intro j refine Fin.cases ?_ (fun j => ?_) j · intro _ exact (hdis i).symm · intro hij exact hpair (by simpa using hij)
Finset.mem_sdiff.mp- An element in a set difference s \ t belongs to s and does not belong to t.
Finset.mem_erase.mp- An element in s with b removed belongs to s and is not equal to b.
Finset.card_le_one.mpr- A finite set has cardinality at most 1 if every two elements in it are equal.
Finset.mem_filter.mp- An element in {w ∈ s | p(w)} belongs to s and satisfies property p.
Finset.mem_filter.mpr- An element belonging to s and satisfying property p belongs to {w ∈ s | p(w)}.
Finset.mem_union_right- If an element belongs to t, then it belongs to s ∪ t.
Finset.mem_union_left- If an element belongs to s, then it belongs to 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 is at most the sum of their cardinalities: |s ∪ t| ≤ |s| + |t|.
Finset.card_singleton- A singleton set {a} has cardinality 1.
Finset.disjoint_left.mpr- Two sets are disjoint if no element of the first set belongs to the second set.
Fin.cases- Performs case analysis on an index in Fin (n + 1), separating the 0 element from successor elements.
- In Step 3, the linear arithmetic inequality d ≤ |N⁺(x) ∩ T| is closed automatically by `omega` using the bounds |N⁺(x)| ≥ d + 2 and |A ∪ {v}| ≤ 2.
- In Step 5, the construction of the (k + 1)-cycle family and the case analysis verifying pairwise disjointness are expressed formally via `Fin.cases`.
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_clean_outneighborhood_cycle_packing_step (α : Type) [Fintype α] [DecidableEq α] (D : Digraph α) [DecidableRel D.Adj] (k d : ℕ) (hloop : ∀ v, ¬ D.Adj v v) (hori : ∀ u v, D.Adj u v → ¬ D.Adj v u) (hdeg : ∀ v, d + 2 ≤ (Finset.univ.filter fun w => D.Adj v w).card) (hpack : ∀ T : Finset α, T.Nonempty → (∀ v ∈ T, d ≤ (T.filter fun w => D.Adj v w).card) → ∃ s : Fin k → Finset α, (∀ i, s i ⊆ T ∧ digraph_directed_cycle_on D (s i)) ∧ Pairwise (fun i j => Disjoint (s i) (s j))) (v : α) (C : Finset α) (hC : digraph_directed_cycle_on D C) (hCout : ∀ w ∈ C, D.Adj v w) (hclean : ∀ a b, a ≠ b → D.Adj v a → D.Adj v b → ∀ x, D.Adj x a → D.Adj x b → x = v) (p : α) (hpv : D.Adj p v) : ∃ s : Fin (k + 1) → Finset α, (∀ i, digraph_directed_cycle_on D (s i)) ∧ Pairwise (fun i j => Disjoint (s i) (s j)) := by classical let T : Finset α := (Finset.univ.erase v) \ C have hpne : p ≠ v := by intro h; subst p; exact hloop v hpv have hpC : p ∉ C := by intro hp exact (hori p v hpv) (hCout p hp) have hT : T.Nonempty := by refine ⟨p, ?_⟩ simp [T, hpne, hpC] have hTdeg : ∀ x ∈ T, d ≤ (T.filter fun w => D.Adj x w).card := by intro x hx have hxne : x ≠ v := by have := (Finset.mem_sdiff.mp hx).1 exact (Finset.mem_erase.mp this).1 let A : Finset α := C.filter fun w => D.Adj x w have hA : A.card ≤ 1 := by apply Finset.card_le_one.mpr intro a ha b hb have haC : a ∈ C := (Finset.mem_filter.mp ha).1 have hbC : b ∈ C := (Finset.mem_filter.mp hb).1 have hxa : D.Adj x a := (Finset.mem_filter.mp ha).2 have hxb : D.Adj x b := (Finset.mem_filter.mp hb).2 by_contra hab exact hxne (hclean a b hab (hCout a haC) (hCout b hbC) x hxa hxb) have hs : (Finset.univ.filter fun w => D.Adj x w) ⊆ (T.filter fun w => D.Adj x w) ∪ (A ∪ {v}) := by intro w hw have hwadj := (Finset.mem_filter.mp hw).2 by_cases hwv : w = v · simp [hwv] by_cases hwC : w ∈ C · have hwA : w ∈ A := Finset.mem_filter.mpr ⟨hwC, hwadj⟩ exact Finset.mem_union_right _ (Finset.mem_union_left _ hwA) · have hwT : w ∈ T := by simp [T, hwv, hwC] exact Finset.mem_union_left _ (Finset.mem_filter.mpr ⟨hwT, hwadj⟩) have hsub := Finset.card_le_card hs have hunion := Finset.card_union_le (T.filter fun w => D.Adj x w) (A ∪ {v}) have hsmall := Finset.card_union_le A ({v} : Finset α) have hd := hdeg x simp only [Finset.card_singleton] at hsmall omega obtain ⟨t, ht, hpair⟩ := hpack T hT hTdeg have hdis : ∀ i, Disjoint C (t i) := by intro i apply Finset.disjoint_left.mpr intro x hx hxt have hxT := (ht i).1 hxt exact (Finset.mem_sdiff.mp hxT).2 hx let f : Fin (k + 1) → Finset α := Fin.cases C t refine ⟨f, ?_, ?_⟩ · intro i refine Fin.cases ?_ (fun i => ?_) i · exact hC · exact (ht i).2 · intro i refine Fin.cases ?_ (fun i => ?_) i · intro j refine Fin.cases ?_ (fun j => ?_) j · intro hij exact (hij rfl).elim · intro _ exact hdis j · intro j refine Fin.cases ?_ (fun j => ?_) j · intro _ exact (hdis i).symm · intro hij exact hpair (by simpa using hij)