AFTD Auto-Formalizing Theoretical Domains

digraph_four_cycles_two_triangles_few_bad

theoremverified

Suppose a finite loopless digraph has minimum outdegree at least seven and contains two disjoint directed triangles. If no outside vertex has six out-neighbors in their union, at most two outside vertices have five out-neighbors in their union, and the displayed robust two-cycle theorem holds on induced subsets, then the digraph contains four disjoint directed cycles.

Statement

theorem digraph_four_cycles_two_triangles_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₂)
    (hcard₁ : C₁.card = 3) (hcard₂ : C₂.card = 3)
    (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
Two-triangle deletion mechanism for OP-110, using the degree-defect two-cycle theorem DOI:10.1137/080715792 Theorem 3.
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…

The proof, explained

The proof finds four disjoint directed cycles by keeping the two given disjoint triangles C₁ and C₂ and finding two additional disjoint cycles in the complement T = V \ (C₁ ∪ C₂). Because |C₁ ∪ C₂| = 6 and the minimum outdegree is at least 7, T is nonempty, every vertex in T has outdegree at least 2 into T, and at most two vertices in T have outdegree exactly 2 into T. These conditions allow applying the assumed robust two-cycle theorem on T, yielding two disjoint cycles in T that are automatically disjoint from C₁ and C₂.

  1. Let U = C₁ ∪ C₂ and T = V \ U; the set U has cardinality 6.

    Define U as the union of the two disjoint triangles C₁ and C₂, and T as the remaining vertices. Because C₁ and C₂ each have 3 vertices and are disjoint, their union U has |U| = 3 + 3 = 6 vertices by Finset.card_union_of_disjoint.

    lines 18–21

    uses Finset.card_union_of_disjoint

      let U := C₁ ∪ C₂
      let T := Finset.univ \ U
      have hU : U.card = 6 := by
        simp [U, Finset.card_union_of_disjoint hdis, hcard₁, hcard₂]
  2. Every vertex in the digraph belongs to either T or U.

    For any vertex x, either x ∈ U (the right disjunct) or x ∉ U, in which case x belongs to T = V \ U by definition (the left disjunct).

    lines 22–26

    uses Or.inl, Or.inr

      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])
  3. The complementary vertex set T is nonempty.

    Suppose for contradiction that T is empty. Then every vertex belongs to U, so the entire vertex set V satisfies |V| ≤ |U| = 6 by Finset.card_le_card. However, since the vertex type is nonempty, choosing any vertex a shows its outdegree is at least 7 by the minimum degree hypothesis (hdeg). Since its out-neighborhood is a subset of V by Finset.filter_subset, we obtain 7 ≤ |V| ≤ 6, a contradiction.

    lines 27–40

    uses Finset.not_nonempty_iff_eq_empty.mp, Finset.card_le_card, Finset.filter_subset

      have hT : T.Nonempty := by
        by_contra hn
        have he : T = ∅ := Finset.not_nonempty_iff_eq_empty.mp hn
        have hs : (Finset.univ : Finset α) ⊆ U := by
          intro x hx
          rcases hcover x with h | h
          · rw [he] at h
            simp at h
          · exact h
        have hc := Finset.card_le_card hs
        obtain ⟨a⟩ := ‹Nonempty α›
        have hd := hdeg a
        have hdu := Finset.card_le_card (Finset.filter_subset (fun w => D.Adj a w) Finset.univ)
        omega
  4. For every vertex x, its out-neighbors partition into those in T and those in U.

    Every out-neighbor w of x lies in either T or U by the coverage property. If w ∈ T, it is an out-neighbor in T; if w ∈ U, it is an out-neighbor in U. Thus the full out-neighborhood is a subset of the union of the out-neighborhoods in T and in U.

    lines 41–48

    uses Finset.mem_filter.mp, Finset.mem_filter.mpr, Finset.mem_union_left, 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⟩)
  5. Every vertex in T has at least 2 out-neighbors in T.

    Let x ∈ T. Because x ∉ U, the hypothesis hnoall guarantees that x has at most 5 out-neighbors in U. The total outdegree of x is at least 7 by hdeg, and it is at most the sum of its outdegrees into T and into U by Finset.card_union_le. Thus its outdegree into T is at least 7 - 5 = 2.

    lines 49–56

    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
  6. At most two vertices in T have outdegree exactly 2 in T.

    If a vertex x ∈ T has outdegree exactly 2 into T, then since its total outdegree is at least 7, it must have at least 7 - 2 = 5 out-neighbors in U. Therefore, the set of vertices in T with outdegree 2 into T is a subset of the vertices in T with at least 5 out-neighbors in U. By hypothesis hfew, there are at most 2 such vertices.

    lines 57–69

    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
  7. There exist two disjoint directed cycles t₀, t₁ entirely contained in T.

    Since T is nonempty, every vertex in T has outdegree at least 2 in T, and at most two vertices in T have outdegree 2 in T, the robust two-cycle hypothesis (hrobust) applies to the induced subgraph on T. This yields two disjoint directed cycles t₀, t₁ ⊆ T.

    line 70

      obtain ⟨t, ht, hpair⟩ := hrobust T hT hTdeg hbad
  8. Both cycles t₀ and t₁ are disjoint from C₁ and C₂.

    Each cycle tᵢ is contained in T. Since T = V \ (C₁ ∪ C₂), no vertex in tᵢ belongs to C₁ or C₂. By Finset.disjoint_left.mpr, this implies that tᵢ is disjoint from C₁ and from C₂.

    lines 71–84

    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)
  9. The four sets C₁, C₂, t₀, t₁ form a family of four directed cycles.

    Define the map f : Fin 4 → Finset α by 0 ↦ C₁, 1 ↦ C₂, 2 ↦ t₀, and 3 ↦ t₁ via Fin.cases. Exhaustive check on the four indices confirms each f i is a directed cycle: C₁ and C₂ by the theorem hypotheses (hC₁, hC₂), and t₀ and t₁ from the robust hypothesis output.

    lines 85–92

    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
  10. The four directed cycles are pairwise disjoint.

    For any distinct indices i ≠ j in {0, 1, 2, 3}, disjointness is verified by cases. Disjointness between C₁ and C₂ comes from hdis; disjointness between C₁ or C₂ and either t₀ or t₁ comes from hdis₁ and hdis₂; and disjointness between t₀ and t₁ comes from the pairwise disjointness of t (hpair).

    lines 93–109

      · 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
Defines a function on Fin (n + 1) by giving its value at 0 and its values on the successors of Fin n.
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_union_of_disjoint
The cardinality of the union of two disjoint finite sets is the sum of their cardinalities: |S ∪ T| = |S| + |T|.
Finset.disjoint_left.mpr
Two finite sets are disjoint if no element of the first belongs to the second.
Finset.filter_subset
Filtering a finite set by a predicate produces a subset of the original set.
Finset.mem_filter.mp
If an element belongs to a filtered set, then it belongs to the base set and satisfies the predicate.
Finset.mem_filter.mpr
If an element belongs to a set and satisfies a predicate, then it belongs to the filtered set.
Finset.mem_union_left
An element in S also belongs to S ∪ T.
Finset.mem_union_right
An element in T also belongs to S ∪ T.
Finset.not_nonempty_iff_eq_empty.mp
A finite set that is not nonempty is empty.
Or.inl
From a proof of A, establishes the disjunction A ∨ B.
Or.inr
From a proof of B, establishes the disjunction A ∨ B.

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_two_triangles_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₂)    (hcard₁ : C₁.card = 3) (hcard₂ : C₂.card = 3)    (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 hU : U.card = 6 := by    simp [U, Finset.card_union_of_disjoint hdis, hcard₁, hcard₂]  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 := by    by_contra hn    have he : T = ∅ := Finset.not_nonempty_iff_eq_empty.mp hn    have hs : (Finset.univ : Finset α) ⊆ U := by      intro x hx      rcases hcover x with h | h      · rw [he] at h        simp at h      · exact h    have hc := Finset.card_le_card hs    obtain ⟨a⟩ := ‹Nonempty α›    have hd := hdeg a    have hdu := Finset.card_le_card (Finset.filter_subset (fun w => D.Adj a w) Finset.univ)    omega  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