AFTD Auto-Formalizing Theoretical Domains

digraph_cycle_packing_from_small_directed_cut

theoremverified

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.

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

    lines 15–27

    uses Finset.mem_filter.mp, Finset.mem_filter.mpr, Finset.mem_union_left, Finset.mem_union_right, Finset.card_le_card, Finset.card_union_le

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

    line 28

      obtain ⟨t, ht, hpair⟩ := hprev B hB hBdeg
  3. The 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.

    lines 29–36

    uses Finset.disjoint_left.mpr

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

    lines 37–42

    uses Fin.cases

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

    lines 43–57

    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.

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