AFTD Auto-Formalizing Theoretical Domains

digraph_clean_outneighborhood_cycle_packing_step

theoremverified

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

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.

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

    lines 17–25

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

    lines 26–40

    uses Finset.mem_sdiff.mp, Finset.mem_erase.mp, Finset.card_le_one.mpr, Finset.mem_filter.mp

      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)
  3. 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.

    lines 41–57

    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_singleton

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

    lines 58–64

    uses Finset.disjoint_left.mpr, Finset.mem_sdiff.mp

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

    lines 65–84

    uses Fin.cases

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

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

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