AFTD Auto-Formalizing Theoretical Domains

digraph_four_cycles_from_undominated_triangle

theoremverified

If a finite digraph of minimum outdegree at least seven has a directed triangle that no outside vertex dominates and the displayed three-cycle condition holds on induced subsets, then it has four pairwise vertex-disjoint directed cycles.

Statement

theorem digraph_four_cycles_from_undominated_triangle
    (α : Type) [Fintype α] [DecidableEq α] [Nonempty α]
    (D : Digraph α) [DecidableRel D.Adj]
    (hdeg : ∀ v, 7 ≤ (Finset.univ.filter fun w => D.Adj v w).card)
    (hthree : ∀ T : Finset α, T.Nonempty →
      (∀ v ∈ T, 5 ≤ (T.filter fun w => D.Adj v w).card) →
      ∃ s : Fin 3 → Finset α, (∀ i, s i ⊆ T ∧ digraph_directed_cycle_on D (s i)) ∧
        Pairwise (fun i j => Disjoint (s i) (s j)))
    (C : Finset α) (hC : digraph_directed_cycle_on D C) (hcard : C.card = 3)
    (hnotdom : ∀ v ∉ C, (C.filter fun w => D.Adj v w).card ≤ 2) :
    ∃ s : Fin 4 → Finset α, (∀ i, digraph_directed_cycle_on D (s i)) ∧
      Pairwise (fun i j => Disjoint (s i) (s j))
Source
Triangle-deletion step toward OP-110 using the outdegree-five three-cycle 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…

The proof, explained

The proof removes the directed triangle C from the digraph to consider the induced subgraph on T = V \ C. Because no outside vertex dominates C (each has at most two out-neighbors in C), every vertex in T retains an out-degree of at least 7 - 2 = 5 into T, which also implies T is nonempty. Applying the three-cycle condition to T yields three pairwise vertex-disjoint directed cycles contained in T. Combining these three cycles with the original triangle C produces four pairwise vertex-disjoint directed cycles in the whole digraph.

  1. The vertex set T = V \ C outside the triangle C is nonempty.

    Define T as the complement of C in the vertex set V. If T were empty, then all vertices of the graph would belong to C, giving |V| ≤ |C| = 3. But since the graph is nonempty, taking any vertex a gives at least 7 out-neighbors, forcing |V| ≥ 7. Linear integer arithmetic (`omega`) derives False from 7 ≤ |V| ≤ 3.

    lines 13–28

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

      let T := Finset.univ \ C
      have hT : T.Nonempty := by
        by_contra hn
        have he : T = ∅ := Finset.not_nonempty_iff_eq_empty.mp hn
        have hs : (Finset.univ : Finset α) ⊆ C := by
          intro x hx
          by_cases hxc : x ∈ C
          · exact hxc
          have hxT : x ∈ T := by simp [T, hxc]
          rw [he] at hxT
          simp at hxT
        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
  2. Every vertex in T has out-degree at least 5 into T.

    For any vertex x ∈ T, we have x ∉ C, so by the non-domination hypothesis `hnotdom`, x has at most 2 out-neighbors in C. The total out-neighborhood of x (which has cardinality at least 7) is covered by the union of its out-neighbors in T and its out-neighbors in C. Therefore, the out-degree into T is at least 7 - 2 = 5, as verified by `omega`.

    lines 29–44

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

      have hTdeg : ∀ x ∈ T, 5 ≤ (T.filter fun w => D.Adj x w).card := by
        intro x hx
        have hxc : x ∉ C := by simpa [T] using hx
        have h2 := hnotdom x hxc
        have hs : (Finset.univ.filter fun w => D.Adj x w) ⊆
            (T.filter fun w => D.Adj x w) ∪ (C.filter fun w => D.Adj x w) := by
          intro w hw
          have hadj := (Finset.mem_filter.mp hw).2
          by_cases hwc : w ∈ C
          · exact Finset.mem_union_right _ (Finset.mem_filter.mpr ⟨hwc, hadj⟩)
          · have hwT : w ∈ T := by simp [T, hwc]
            exact Finset.mem_union_left _ (Finset.mem_filter.mpr ⟨hwT, hadj⟩)
        have hc := Finset.card_le_card hs
        have hu := Finset.card_union_le (T.filter fun w => D.Adj x w) (C.filter fun w => D.Adj x w)
        have hd := hdeg x
        omega
  3. There exist three pairwise vertex-disjoint directed cycles in T, each disjoint from C.

    Applying the induction hypothesis `hthree` to the nonempty set T with minimum out-degree at least 5 yields a family t of three pairwise disjoint directed cycles contained in T. Since every cycle t(i) is a subset of T = V \ C, no cycle shares any vertex with C.

    lines 45–52

    uses Finset.disjoint_left.mpr

      obtain ⟨t, ht, hpair⟩ := hthree 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
        have hxc : x ∉ C := by simpa [T] using hxT
        exact hxc hx
  4. The family f formed by adjoining C to the three cycles in T consists of four directed cycles in D.

    We define f : Fin 4 → Finset α using `Fin.cases` so that f(0) = C and f(i + 1) = t(i). Exhausting the four possible values of i with `fin_cases` confirms that each f(i) is a directed cycle: f(0) = C is the given directed triangle, and each f(i + 1) = t(i) is one of the three cycles obtained from `hthree`.

    lines 53–60

    uses Fin.cases

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

    For any distinct indices i ≠ j in Fin 4, we verify that f(i) and f(j) are disjoint by exhausting all 16 index pairs with `fin_cases`. The diagonal cases i = j are eliminated by the assumption i ≠ j. When one index is 0 and the other is nonzero, disjointness holds because C is disjoint from each t(k). When both indices are distinct nonzero elements, disjointness follows from the mutual disjointness of the three cycles in t.

    lines 61–79

      · intro i j hij
        have h01 := hpair (show (0 : Fin 3) ≠ 1 by decide)
        have h02 := hpair (show (0 : Fin 3) ≠ 2 by decide)
        have h12 := hpair (show (1 : Fin 3) ≠ 2 by decide)
        fin_cases i <;> fin_cases j <;>
          first
          | exact (hij rfl).elim
          | exact hdis 0
          | exact hdis 1
          | exact hdis 2
          | exact (hdis 0).symm
          | exact (hdis 1).symm
          | exact (hdis 2).symm
          | exact h01
          | exact h02
          | exact h12
          | exact h01.symm
          | exact h02.symm
          | exact h12.symm
Finset.not_nonempty_iff_eq_empty.mp
A finite set is not nonempty only if it is the empty set.
Finset.card_le_card
If a finite set s is a subset of t, then |s| ≤ |t|.
Finset.filter_subset
The subset of elements of s satisfying a given predicate is a subset of s.
Finset.mem_filter.mp
If an element belongs to the filtered set {w ∈ s | p w}, then it belongs to s and satisfies p.
Finset.mem_filter.mpr
If an element belongs to s and satisfies p, then it belongs to the filtered set {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_union_le
The cardinality of the union of two finite sets is at most the sum of their cardinalities: |s ∪ t| ≤ |s| + |t|.
Finset.disjoint_left.mpr
If no element of s belongs to t, then s and t are disjoint.
Fin.cases
Defines a function on Fin (n + 1) by specifying its value at 0 and its values on the successors of elements in Fin n.

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_undominated_triangle    (α : Type) [Fintype α] [DecidableEq α] [Nonempty α]    (D : Digraph α) [DecidableRel D.Adj]    (hdeg : ∀ v, 7 ≤ (Finset.univ.filter fun w => D.Adj v w).card)    (hthree : ∀ T : Finset α, T.Nonempty →      (∀ v ∈ T, 5 ≤ (T.filter fun w => D.Adj v w).card) →      ∃ s : Fin 3 → Finset α, (∀ i, s i ⊆ T ∧ digraph_directed_cycle_on D (s i)) ∧        Pairwise (fun i j => Disjoint (s i) (s j)))    (C : Finset α) (hC : digraph_directed_cycle_on D C) (hcard : C.card = 3)    (hnotdom : ∀ v ∉ C, (C.filter fun w => D.Adj v w).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 T := Finset.univ \ C  have hT : T.Nonempty := by    by_contra hn    have he : T = ∅ := Finset.not_nonempty_iff_eq_empty.mp hn    have hs : (Finset.univ : Finset α) ⊆ C := by      intro x hx      by_cases hxc : x ∈ C      · exact hxc      have hxT : x ∈ T := by simp [T, hxc]      rw [he] at hxT      simp at hxT    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 hTdeg : ∀ x ∈ T, 5 ≤ (T.filter fun w => D.Adj x w).card := by    intro x hx    have hxc : x ∉ C := by simpa [T] using hx    have h2 := hnotdom x hxc    have hs : (Finset.univ.filter fun w => D.Adj x w) ⊆        (T.filter fun w => D.Adj x w) ∪ (C.filter fun w => D.Adj x w) := by      intro w hw      have hadj := (Finset.mem_filter.mp hw).2      by_cases hwc : w ∈ C      · exact Finset.mem_union_right _ (Finset.mem_filter.mpr ⟨hwc, hadj⟩)      · have hwT : w ∈ T := by simp [T, hwc]        exact Finset.mem_union_left _ (Finset.mem_filter.mpr ⟨hwT, hadj⟩)    have hc := Finset.card_le_card hs    have hu := Finset.card_union_le (T.filter fun w => D.Adj x w) (C.filter fun w => D.Adj x w)    have hd := hdeg x    omega  obtain ⟨t, ht, hpair⟩ := hthree 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    have hxc : x ∉ C := by simpa [T] using hxT    exact hxc hx  let f : Fin 4 → Finset α := Fin.cases C t  refine ⟨f, ?_, ?_⟩  · intro i    fin_cases i    · exact hC    · exact (ht 0).2    · exact (ht 1).2    · exact (ht 2).2  · intro i j hij    have h01 := hpair (show (0 : Fin 3) ≠ 1 by decide)    have h02 := hpair (show (0 : Fin 3) ≠ 2 by decide)    have h12 := hpair (show (1 : Fin 3) ≠ 2 by decide)    fin_cases i <;> fin_cases j <;>      first      | exact (hij rfl).elim      | exact hdis 0      | exact hdis 1      | exact hdis 2      | exact (hdis 0).symm      | exact (hdis 1).symm      | exact (hdis 2).symm      | exact h01      | exact h02      | exact h12      | exact h01.symm      | exact h02.symm      | exact h12.symm
See it in the graphDiscuss this resultChallenge it