AFTD Auto-Formalizing Theoretical Domains

digraph_four_cycles_from_two_cycles_few_bad

theoremverified

Two disjoint directed cycles with nonempty remainder can be extended to four under the displayed robust two-cycle condition if each outside vertex has at most five out-neighbors in their union and at most two have five.

Statement

theorem digraph_four_cycles_from_two_cycles_few_bad
    (α : Type) [Fintype α] [DecidableEq α] [Nonempty α]
    (D : Digraph α) [DecidableRel D.Adj] (hloop : ∀ v, ¬ D.Adj v v)
    (hdeg : ∀ v, 7 ≤ (Finset.univ.filter fun w => D.Adj v w).card)
    (hrobust : ∀ T : Finset α, T.Nonempty →
      (∀ v ∈ T, 2 ≤ (T.filter fun w => D.Adj v w).card) →
      (T.filter fun v => (T.filter fun w => D.Adj v w).card = 2).card ≤ 2 →
      ∃ s : Fin 2 → Finset α, (∀ i, s i ⊆ T ∧ digraph_directed_cycle_on D (s i)) ∧
        Pairwise (fun i j => Disjoint (s i) (s j)))
    (C₁ C₂ : Finset α) (hC₁ : digraph_directed_cycle_on D C₁)
    (hC₂ : digraph_directed_cycle_on D C₂) (hdis : Disjoint C₁ C₂)
    (hTne : (Finset.univ \ (C₁ ∪ C₂)).Nonempty)
    (hnoall : ∀ v ∉ (C₁ ∪ C₂), ((C₁ ∪ C₂).filter fun w => D.Adj v w).card ≤ 5)
    (hfew : ((Finset.univ \ (C₁ ∪ C₂)).filter fun v =>
      5 ≤ ((C₁ ∪ C₂).filter fun w => D.Adj v w).card).card ≤ 2) :
    ∃ s : Fin 4 → Finset α, (∀ i, digraph_directed_cycle_on D (s i)) ∧
      Pairwise (fun i j => Disjoint (s i) (s j))
Source
General cycle-pair deletion reduction for OP-110; the robust two-cycle hypothesis is a published theorem.
Verified
02 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 1

The proof, explained

Given two disjoint directed cycles C₁ and C₂, the strategy is to apply the robust two-cycle hypothesis to the remaining vertex set T = V \ (C₁ ∪ C₂) to find two additional disjoint cycles. Because every vertex has out-degree at least 7 and at most 5 out-neighbors in C₁ ∪ C₂, each vertex in T has out-degree at least 7 - 5 = 2 restricted to T. Furthermore, any vertex in T with restricted out-degree exactly 2 must have at least 5 out-neighbors in C₁ ∪ C₂, which the hypotheses limit to at most two vertices. The robust hypothesis therefore produces two disjoint directed cycles inside T, which are disjoint from C₁ and C₂ by construction, yielding four pairwise disjoint directed cycles.

  1. Let U = C₁ ∪ C₂ and T = V \ U; every vertex lies in T or U, and T is nonempty.

    We define U as the union of the two given cycles and T as the remaining vertex set. By case analysis on whether a vertex belongs to U, every vertex lies in T or U. Nonemptiness of T is given directly by hypothesis hTne.

    lines 18–25

    uses Or.inr, Or.inl

      let U := C₁ ∪ C₂
      let T := Finset.univ \ U
      have hcover : ∀ x : α, x ∈ T ∨ x ∈ U := by
        intro x
        by_cases hx : x ∈ U
        · exact Or.inr hx
        · exact Or.inl (by simp [T, hx])
      have hT : T.Nonempty := hTne
  2. For every vertex x, its out-neighbors in the graph are covered by its out-neighbors in T and its out-neighbors in U.

    Any out-neighbor w of x lies in either T or U. Hence w is either an out-neighbor in T or an out-neighbor in U, so the full out-neighborhood is contained in the union of the two restricted out-neighborhoods.

    lines 26–33

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

      have hsplit : ∀ x : α,
          (Finset.univ.filter fun w => D.Adj x w) ⊆
            (T.filter fun w => D.Adj x w) ∪ (U.filter fun w => D.Adj x w) := by
        intro x w hw
        have hadj := (Finset.mem_filter.mp hw).2
        rcases hcover w with h | h
        · exact Finset.mem_union_left _ (Finset.mem_filter.mpr ⟨h, hadj⟩)
        · exact Finset.mem_union_right _ (Finset.mem_filter.mpr ⟨h, hadj⟩)
  3. Every vertex in T has at least 2 out-neighbors in T.

    For any vertex x in T, x is not in U. By hypothesis hnoall, x has at most 5 out-neighbors in U. Since the total out-degree of x is at least 7 by hdeg, and the out-neighbors are covered by T and U, the cardinality of the out-neighborhood in T must be at least 7 - 5 = 2 by linear arithmetic (omega).

    lines 34–41

    uses Finset.card_le_card, Finset.card_union_le

      have hTdeg : ∀ x ∈ T, 2 ≤ (T.filter fun w => D.Adj x w).card := by
        intro x hx
        have hxU : x ∉ U := by simpa [T] using hx
        have h5 : (U.filter fun w => D.Adj x w).card ≤ 5 := hnoall x hxU
        have hc := Finset.card_le_card (hsplit x)
        have hu := Finset.card_union_le (T.filter fun w => D.Adj x w) (U.filter fun w => D.Adj x w)
        have hd := hdeg x
        omega
  4. At most two vertices in T have out-degree exactly 2 in T.

    If a vertex x in T has out-degree 2 in T, then because its total out-degree is at least 7, it must send at least 7 - 2 = 5 edges to U. Thus the set of degree-2 vertices in T is a subset of those with at least 5 out-neighbors in U. By hypothesis hfew, this set has at most 2 vertices, so by subset monotonicity of cardinality, at most 2 vertices in T have out-degree 2 in T.

    lines 42–54

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

      have hbad : (T.filter fun v => (T.filter fun w => D.Adj v w).card = 2).card ≤ 2 := by
        have hs : (T.filter fun v => (T.filter fun w => D.Adj v w).card = 2) ⊆
            (T.filter fun v => 5 ≤ (U.filter fun w => D.Adj v w).card) := by
          intro x hx
          obtain ⟨hxT, hxdeg⟩ := Finset.mem_filter.mp hx
          apply Finset.mem_filter.mpr
          refine ⟨hxT, ?_⟩
          have hc := Finset.card_le_card (hsplit x)
          have hu := Finset.card_union_le (T.filter fun w => D.Adj x w) (U.filter fun w => D.Adj x w)
          have hd := hdeg x
          omega
        have hh := Finset.card_le_card hs
        exact hh.trans hfew
  5. The robust two-cycle hypothesis yields two disjoint directed cycles in T.

    The set T is nonempty, every vertex in T has out-degree at least 2 within T, and at most two vertices have out-degree 2 in T. These are precisely the preconditions of hrobust, so applying it produces two directed cycles t₀, t₁ contained in T that are disjoint.

    line 55

      obtain ⟨t, ht, hpair⟩ := hrobust T hT hTdeg hbad
  6. The two cycles in T are each disjoint from C₁ and from C₂.

    Each cycle t(i) is a subset of T, which is disjoint from U = C₁ ∪ C₂. Thus no vertex of t(i) can lie in C₁ or C₂. Applying Finset.disjoint_left.mpr proves that C₁ is disjoint from t(i) and C₂ is disjoint from t(i).

    lines 56–69

    uses Finset.disjoint_left.mpr, Finset.mem_union_left, Finset.mem_union_right

      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
        have hxU : x ∉ U := by simpa [T] using hxT
        exact hxU (Finset.mem_union_left _ hx)
      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
        have hxU : x ∉ U := by simpa [T] using hxT
        exact hxU (Finset.mem_union_right _ hx)
  7. Assemble C₁, C₂, and the two new cycles into a 4-cycle family f and verify that each is a directed cycle.

    We define f : Fin 4 → Finset α sending 0 to C₁, 1 to C₂, 2 to t₀, and 3 to t₁ using Fin.cases. Checking each index with fin_cases confirms that each component is a directed cycle, using hypotheses hC₁, hC₂ and the cycle property from the robust construction.

    lines 70–77

    uses Fin.cases

      let f : Fin 4 → Finset α := Fin.cases C₁ (Fin.cases C₂ t)
      refine ⟨f, ?_, ?_⟩
      · intro i
        fin_cases i
        · exact hC₁
        · exact hC₂
        · exact (ht 0).2
        · exact (ht 1).2
  8. The four directed cycles in f are pairwise disjoint.

    For indices i ≠ j, exhaustive case analysis on (i, j) with fin_cases disposes of the diagonal i = j by contradiction and resolves all off-diagonal pairs using the disjointness of C₁ and C₂, the disjointness of C₁ and t(k), the disjointness of C₂ and t(k), or the mutual disjointness of t₀ and t₁, applying symmetry where appropriate.

    lines 78–94

      · intro i j hij
        have ht01 := hpair (show (0 : Fin 2) ≠ 1 by decide)
        fin_cases i <;> fin_cases j <;>
          first
          | exact (hij rfl).elim
          | exact hdis
          | exact hdis.symm
          | exact hdis₁ 0
          | exact hdis₁ 1
          | exact (hdis₁ 0).symm
          | exact (hdis₁ 1).symm
          | exact hdis₂ 0
          | exact hdis₂ 1
          | exact (hdis₂ 0).symm
          | exact (hdis₂ 1).symm
          | exact ht01
          | exact ht01.symm
Fin.cases
Case analysis or recursion on Fin (n + 1), defined by a value at 0 and values at each successor
Finset.card_le_card
If a finite set s is a subset of t, then the cardinality of s is at most the cardinality of t
Finset.card_union_le
The cardinality of the union of two finite sets is at most the sum of their cardinalities
Finset.disjoint_left.mpr
Two finite sets are disjoint if no element of the first belongs to the second
Finset.mem_filter.mp
An element of a filtered set {x ∈ s | p x} belongs to s and satisfies p
Finset.mem_filter.mpr
An element that belongs to s and satisfies predicate p belongs to the filtered set {x ∈ s | p x}
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
Or.inl
Left introduction rule for disjunction: if a holds, then a ∨ b holds
Or.inr
Right introduction rule for disjunction: if b holds, then a ∨ b holds

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_four_cycles_from_two_cycles_few_bad    (α : Type) [Fintype α] [DecidableEq α] [Nonempty α]    (D : Digraph α) [DecidableRel D.Adj] (hloop : ∀ v, ¬ D.Adj v v)    (hdeg : ∀ v, 7 ≤ (Finset.univ.filter fun w => D.Adj v w).card)    (hrobust : ∀ T : Finset α, T.Nonempty →      (∀ v ∈ T, 2 ≤ (T.filter fun w => D.Adj v w).card) →      (T.filter fun v => (T.filter fun w => D.Adj v w).card = 2).card ≤ 2 →      ∃ s : Fin 2 → Finset α, (∀ i, s i ⊆ T ∧ digraph_directed_cycle_on D (s i)) ∧        Pairwise (fun i j => Disjoint (s i) (s j)))    (C₁ C₂ : Finset α) (hC₁ : digraph_directed_cycle_on D C₁)    (hC₂ : digraph_directed_cycle_on D C₂) (hdis : Disjoint C₁ C₂)    (hTne : (Finset.univ \ (C₁ ∪ C₂)).Nonempty)    (hnoall : ∀ v ∉ (C₁ ∪ C₂), ((C₁ ∪ C₂).filter fun w => D.Adj v w).card ≤ 5)    (hfew : ((Finset.univ \ (C₁ ∪ C₂)).filter fun v =>      5 ≤ ((C₁ ∪ C₂).filter fun w => D.Adj v w).card).card ≤ 2) :    ∃ s : Fin 4 → Finset α, (∀ i, digraph_directed_cycle_on D (s i)) ∧      Pairwise (fun i j => Disjoint (s i) (s j)) := by  let U := C₁ ∪ C₂  let T := Finset.univ \ U  have hcover : ∀ x : α, x ∈ T ∨ x ∈ U := by    intro x    by_cases hx : x ∈ U    · exact Or.inr hx    · exact Or.inl (by simp [T, hx])  have hT : T.Nonempty := hTne  have hsplit : ∀ x : α,      (Finset.univ.filter fun w => D.Adj x w) ⊆        (T.filter fun w => D.Adj x w) ∪ (U.filter fun w => D.Adj x w) := by    intro x w hw    have hadj := (Finset.mem_filter.mp hw).2    rcases hcover w with h | h    · exact Finset.mem_union_left _ (Finset.mem_filter.mpr ⟨h, hadj⟩)    · exact Finset.mem_union_right _ (Finset.mem_filter.mpr ⟨h, hadj⟩)  have hTdeg : ∀ x ∈ T, 2 ≤ (T.filter fun w => D.Adj x w).card := by    intro x hx    have hxU : x ∉ U := by simpa [T] using hx    have h5 : (U.filter fun w => D.Adj x w).card ≤ 5 := hnoall x hxU    have hc := Finset.card_le_card (hsplit x)    have hu := Finset.card_union_le (T.filter fun w => D.Adj x w) (U.filter fun w => D.Adj x w)    have hd := hdeg x    omega  have hbad : (T.filter fun v => (T.filter fun w => D.Adj v w).card = 2).card ≤ 2 := by    have hs : (T.filter fun v => (T.filter fun w => D.Adj v w).card = 2) ⊆        (T.filter fun v => 5 ≤ (U.filter fun w => D.Adj v w).card) := by      intro x hx      obtain ⟨hxT, hxdeg⟩ := Finset.mem_filter.mp hx      apply Finset.mem_filter.mpr      refine ⟨hxT, ?_⟩      have hc := Finset.card_le_card (hsplit x)      have hu := Finset.card_union_le (T.filter fun w => D.Adj x w) (U.filter fun w => D.Adj x w)      have hd := hdeg x      omega    have hh := Finset.card_le_card hs    exact hh.trans hfew  obtain ⟨t, ht, hpair⟩ := hrobust T hT hTdeg hbad  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    have hxU : x ∉ U := by simpa [T] using hxT    exact hxU (Finset.mem_union_left _ hx)  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    have hxU : x ∉ U := by simpa [T] using hxT    exact hxU (Finset.mem_union_right _ hx)  let f : Fin 4 → Finset α := Fin.cases C₁ (Fin.cases C₂ t)  refine ⟨f, ?_, ?_⟩  · intro i    fin_cases i    · exact hC₁    · exact hC₂    · exact (ht 0).2    · exact (ht 1).2  · intro i j hij    have ht01 := hpair (show (0 : Fin 2) ≠ 1 by decide)    fin_cases i <;> fin_cases j <;>      first      | exact (hij rfl).elim      | exact hdis      | exact hdis.symm      | exact hdis₁ 0      | exact hdis₁ 1      | exact (hdis₁ 0).symm      | exact (hdis₁ 1).symm      | exact hdis₂ 0      | exact hdis₂ 1      | exact (hdis₂ 0).symm      | exact (hdis₂ 1).symm      | exact ht01      | exact ht01.symm
See it in the graphDiscuss this resultChallenge it