AFTD Auto-Formalizing Theoretical Domains

digraph_four_cycles_from_digon_and_three_cycle_theorem

theoremverified

If a finite loopless digraph has minimum outdegree seven, contains a directed two-cycle, and every nonempty vertex subset whose induced minimum outdegree is five contains three disjoint directed cycles, then it contains four disjoint directed cycles.

Statement

theorem digraph_four_cycles_from_digon_and_three_cycle_theorem
    (α : 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)
    (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)))
    (u v : α) (huv : D.Adj u v) (hvu : D.Adj v u) :
    ∃ s : Fin 4 → Finset α, (∀ i, digraph_directed_cycle_on D (s i)) ∧
      Pairwise (fun i j => Disjoint (s i) (s j))
Source
Digon reduction in the minimum-counterexample route for OP-110, using the published outdegree-five theorem for three cycles.
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

Since the digraph is loopless, the directed 2-cycle between u and v is on two distinct vertices, forming a directed cycle {u, v}. Deleting {u, v} leaves the nonempty vertex subset T = V \ {u, v}, on which every vertex retains an outdegree of at least 7 - 2 = 5. By the three-cycle hypothesis applied to T, there are three pairwise disjoint directed cycles contained in T. Adjoining the disjoint 2-cycle {u, v} yields four pairwise disjoint directed cycles in the digraph.

  1. The vertices u and v are distinct, and T is defined as the set of vertices outside {u, v}.

    Because the digraph has no self-loops (hloop), the existence of a directed edge from u to v implies u ≠ v. We define T = V \ {u, v} by removing u and v from the universal vertex set.

    lines 12–13

      have huvne : u ≠ v := by intro h; subst v; exact hloop u huv
      let T : Finset α := (Finset.univ.erase u).erase v
  2. The vertex set of the digraph has cardinality at least 7.

    The hypothesis hdeg states that every vertex has outdegree at least 7. In particular, the out-neighborhood of u has size at least 7, and since it is a subset of the universal vertex set (Finset.filter_subset), the total number of vertices |V| is at least 7 by monotonicity of cardinality (Finset.card_le_card).

    lines 14–15

    uses Finset.card_le_card, Finset.filter_subset

      have hcard : 7 ≤ (Finset.univ : Finset α).card :=
        (hdeg u).trans (Finset.card_le_card (Finset.filter_subset _ _))
  3. The vertex set T is nonempty.

    Suppose for contradiction that T were empty (Finset.not_nonempty_iff_eq_empty.mp). Then every vertex in V must equal u or v, so V ⊆ {u, v}. By monotonicity of cardinality (Finset.card_le_card), this would mean |V| ≤ |{u, v}| ≤ 2. But |V| ≥ 7, which gives a contradiction via linear arithmetic (omega).

    lines 16–30

    uses Finset.not_nonempty_iff_eq_empty.mp, Finset.card_le_card

      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,v} := by
          intro x hx
          by_cases hxu : x = u
          · simp [hxu]
          by_cases hxv : x = v
          · simp [hxv]
          have : x ∈ T := by simp [T, hxu, hxv]
          rw [he] at this
          simp at this
        have hh := Finset.card_le_card hs
        have hp : ({u,v} : Finset α).card ≤ 2 := by simp [huvne]
        omega
  4. Every vertex in T has at least 5 out-neighbors in T.

    Let x ∈ T. Any out-neighbor w of x in the entire digraph (Finset.mem_filter.mp) is either in {u, v} or in T, so the full out-neighborhood of x is a subset of the union of its out-neighborhood in T and {u, v} (Finset.mem_union_left, Finset.mem_filter.mpr). By subadditivity of cardinality (Finset.card_le_card, Finset.card_union_le), the total outdegree is at most the induced outdegree in T plus |{u, v}| ≤ 2. Since the total outdegree is at least 7 (hdeg), linear arithmetic (omega) implies the induced outdegree in T is at least 5.

    lines 31–47

    uses Finset.mem_filter.mp, Finset.mem_union_left, Finset.mem_filter.mpr, 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 hs : (Finset.univ.filter fun w => D.Adj x w) ⊆
            (T.filter fun w => D.Adj x w) ∪ {u,v} := by
          intro w hw
          have hadj := (Finset.mem_filter.mp hw).2
          by_cases hwu : w = u
          · simp [hwu]
          by_cases hwv : w = v
          · simp [hwv]
          have hwT : w ∈ T := by simp [T, hwu, hwv]
          exact Finset.mem_union_left _ (Finset.mem_filter.mpr ⟨hwT, hadj⟩)
        have hh := Finset.card_le_card hs
        have hu := Finset.card_union_le (T.filter fun w => D.Adj x w) ({u,v} : Finset α)
        have hp : ({u,v} : Finset α).card ≤ 2 := by simp [huvne]
        have hd := hdeg x
        omega
  5. There exist three pairwise disjoint directed cycles contained in T.

    Applying the hypothesis hthree to the nonempty set T and its induced minimum outdegree bound of 5 yields a family t of three directed cycles in D, each contained in T, which are pairwise disjoint.

    line 48

      obtain ⟨t, ht, hpair⟩ := hthree T hT hTdeg
  6. The two-element set {u, v} forms a directed cycle in D.

    We provide the list [u, v] as the cycle. Since u ≠ v and the directed edges u → v and v → u exist, [u, v] is a valid directed 2-cycle on the set {u, v}.

    lines 49–51

      have h2 : digraph_directed_cycle_on D ({u,v} : Finset α) := by
        refine ⟨[u,v], ?_⟩
        simp [huvne, huv, hvu]
  7. The 2-cycle {u, v} is disjoint from each of the three cycles in T.

    To show disjointness (Finset.disjoint_left.mpr), suppose an element x belongs to both {u, v} and t(i). Since t(i) ⊆ T, x ∈ T, which means x ≠ u and x ≠ v (Finset.mem_erase, Finset.mem_univ, and_true). However, x ∈ {u, v} implies x = u or x = v (Finset.mem_insert, Finset.mem_singleton), yielding a contradiction.

    lines 52–59

    uses Finset.disjoint_left.mpr, Finset.mem_erase, Finset.mem_univ, and_true, Finset.mem_insert, Finset.mem_singleton

      have hdis : ∀ i, Disjoint ({u,v} : Finset α) (t i) := by
        intro i
        apply Finset.disjoint_left.mpr
        intro x hx hxt
        have hxT := (ht i).1 hxt
        simp only [T, Finset.mem_erase, Finset.mem_univ, and_true] at hxT
        simp only [Finset.mem_insert, Finset.mem_singleton] at hx
        rcases hx with rfl | rfl <;> simp_all
  8. Construct a family f of four sets by prepending {u, v} to the three cycles from T, and verify each is a directed cycle.

    Using Fin.cases, define f : Fin 4 → Finset α by setting f(0) = {u, v} and f(i+1) = t(i). By casing on i ∈ {0, 1, 2, 3}, f(0) is the 2-cycle {u, v} and f(1), f(2), f(3) are the three directed cycles t(0), t(1), t(2).

    lines 60–67

    uses Fin.cases

      let f : Fin 4 → Finset α := Fin.cases {u,v} t
      refine ⟨f, ?_, ?_⟩
      · intro i
        fin_cases i
        · exact h2
        · exact (ht 0).2
        · exact (ht 1).2
        · exact (ht 2).2
  9. The four directed cycles in f are pairwise disjoint.

    For distinct indices i ≠ j in Fin 4, we examine all pairs. When i = j, the hypothesis i ≠ j gives an immediate contradiction. When one index is 0 and the other is nonzero, disjointness follows from {u, v} being disjoint from each t(k). When both indices are nonzero, disjointness follows from the pairwise disjointness of t(0), t(1), and t(2).

    lines 68–86

      · 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
and_true
For any proposition p, p ∧ True is equivalent to p.
Fin.cases
Defines a function on Fin (n + 1) by specifying its value at 0 and its values on successors i.succ.
Finset.card_le_card
If s ⊆ 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.disjoint_left.mpr
If no element of s belongs to t, then s and t are disjoint.
Finset.mem_erase
An element a belongs to s \ {b} if and only if a ≠ b and a ∈ 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_insert
An element belongs to {b} ∪ s if and only if it equals b or belongs to s.
Finset.mem_singleton
An element belongs to the singleton {a} if and only if it equals a.
Finset.mem_univ
Every element of a finite type belongs to the universal set Finset.univ.
Finset.mem_union_left
If a ∈ s, then a ∈ s ∪ t.
Finset.not_nonempty_iff_eq_empty.mp
If a finite set is not nonempty, then it is the empty set.
Finset.filter_subset
The subset of elements of s satisfying a predicate p is a subset of s.

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_digon_and_three_cycle_theorem    (α : 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)    (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)))    (u v : α) (huv : D.Adj u v) (hvu : D.Adj v u) :    ∃ s : Fin 4 → Finset α, (∀ i, digraph_directed_cycle_on D (s i)) ∧      Pairwise (fun i j => Disjoint (s i) (s j)) := by  have huvne : u ≠ v := by intro h; subst v; exact hloop u huv  let T : Finset α := (Finset.univ.erase u).erase v  have hcard : 7 ≤ (Finset.univ : Finset α).card :=    (hdeg u).trans (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,v} := by      intro x hx      by_cases hxu : x = u      · simp [hxu]      by_cases hxv : x = v      · simp [hxv]      have : x ∈ T := by simp [T, hxu, hxv]      rw [he] at this      simp at this    have hh := Finset.card_le_card hs    have hp : ({u,v} : Finset α).card ≤ 2 := by simp [huvne]    omega  have hTdeg : ∀ x ∈ T, 5 ≤ (T.filter fun w => D.Adj x w).card := by    intro x hx    have hs : (Finset.univ.filter fun w => D.Adj x w) ⊆        (T.filter fun w => D.Adj x w) ∪ {u,v} := by      intro w hw      have hadj := (Finset.mem_filter.mp hw).2      by_cases hwu : w = u      · simp [hwu]      by_cases hwv : w = v      · simp [hwv]      have hwT : w ∈ T := by simp [T, hwu, hwv]      exact Finset.mem_union_left _ (Finset.mem_filter.mpr ⟨hwT, hadj⟩)    have hh := Finset.card_le_card hs    have hu := Finset.card_union_le (T.filter fun w => D.Adj x w) ({u,v} : Finset α)    have hp : ({u,v} : Finset α).card ≤ 2 := by simp [huvne]    have hd := hdeg x    omega  obtain ⟨t, ht, hpair⟩ := hthree T hT hTdeg  have h2 : digraph_directed_cycle_on D ({u,v} : Finset α) := by    refine ⟨[u,v], ?_⟩    simp [huvne, huv, hvu]  have hdis : ∀ i, Disjoint ({u,v} : Finset α) (t i) := by    intro i    apply Finset.disjoint_left.mpr    intro x hx hxt    have hxT := (ht i).1 hxt    simp only [T, Finset.mem_erase, Finset.mem_univ, and_true] at hxT    simp only [Finset.mem_insert, Finset.mem_singleton] at hx    rcases hx with rfl | rfl <;> simp_all  let f : Fin 4 → Finset α := Fin.cases {u,v} t  refine ⟨f, ?_, ?_⟩  · intro i    fin_cases i    · exact h2    · 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