AFTD Auto-Formalizing Theoretical Domains

digraph_four_cycles_from_small_cut

theoremverified

In a loopless digraph of minimum outdegree seven, if B is nonempty and all arcs leaving B end in a set S of at most two vertices, a directed cycle in the in-neighborhood of a vertex outside B and S combines with three directed cycles in B to give four disjoint cycles, provided the displayed outdegree-five theorem holds.

Statement

theorem digraph_four_cycles_from_small_cut
    (α : 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)))
    (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) :
    ∃ s : Fin 4 → Finset α, (∀ i, digraph_directed_cycle_on D (s i)) ∧
      Pairwise (fun i j => Disjoint (s i) (s j))
Source
Adaptation of the strong-connectivity argument in arXiv:1805.02999, Section 3, to the four-cycle minimum-counterexample route for OP-110.
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 constructs four pairwise disjoint directed cycles by combining the given cycle C with three disjoint cycles inside B. First, because every arc leaving B ends in B or S and |S| ≤ 2, each vertex in B retains at least 7 - 2 = 5 out-neighbors in B, satisfying the outdegree-5 theorem hypothesis to obtain three disjoint directed cycles in B. Finally, the cycle C must be disjoint from all three cycles in B because any vertex in C has an arc to a, which cannot originate in B since a is outside both B and S.

  1. Every vertex in B has at least 5 out-neighbors in B.

    For any vertex b ∈ B, the cut condition (hcut) implies that every out-neighbor of b lies in B ∪ S. Hence, the out-neighborhood of b in the entire digraph is a subset of its out-neighborhood in B united with S. Since the outdegree of b in the digraph is at least 7 (hdeg) and |S| ≤ 2 (hS), subadditivity of cardinality (Finset.card_union_le) and subset monotonicity (Finset.card_le_card) imply that b has at least 7 - 2 = 5 out-neighbors in B. Linear integer arithmetic (omega) finishes the calculation.

    lines 16–28

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

      have hBdeg : ∀ b ∈ B, 5 ≤ (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 exist three pairwise disjoint directed cycles contained entirely in B.

    Since B is nonempty and each vertex in B has outdegree at least 5 within B, the hypothesis hthree applies to B, yielding a family t of three directed cycles in B that are pairwise disjoint.

    line 29

      obtain ⟨t, ht, hpair⟩ := hthree B hB hBdeg
  3. The cycle C is disjoint from each of the three cycles in B.

    To show C is disjoint from t(i) (via Finset.disjoint_left.mpr), suppose for contradiction that some vertex x lies in both C and t(i). Because t(i) ⊆ B, x must belong to B. The assumption hin gives an arc from x to a. But the cut condition hcut forces any arc out of B to land in B or S, meaning a ∈ B or a ∈ S. This directly contradicts the hypotheses that a ∉ B and a ∉ S.

    lines 30–37

    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. Combining C with the three cycles in B gives a 4-element family of directed cycles.

    We define f : Fin 4 → Finset α using Fin.cases by placing C at index 0 and t at indices 1, 2, 3. Case analysis on i : Fin 4 shows that f(0) is a directed cycle by hC, and f(1), f(2), f(3) are directed cycles by the properties of t.

    lines 38–45

    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 cycles in f are pairwise disjoint.

    For distinct indices i ≠ j in Fin 4, we establish Disjoint (f i) (f j). The pairwise disjointness of t(0), t(1), t(2) is extracted from hpair. An exhaustive case split on all pairs (i, j) then shows disjointness: the diagonal i = j is ruled out by i ≠ j; cases with one index equal to 0 follow from the disjointness of C from each t(k); and cases with both indices in {1, 2, 3} follow from the pairwise disjointness of the cycles in t.

    lines 46–64

      · 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
Fin.cases
Defines a dependent function on Fin (n + 1) by its value at 0 and its values on the remaining n elements.
Finset.card_le_card
If one finite set is a subset of another, its cardinality is less than or equal to that of the other.
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 set belongs to the second set.
Finset.mem_filter.mp
If an element belongs to a filtered finite set, then it belongs to the base set and satisfies the predicate.
Finset.mem_filter.mpr
If an element belongs to a finite set and satisfies a predicate, then it belongs to the filtered finite set.
Finset.mem_union_left
An element in a finite set s also belongs to the union s ∪ t.
Finset.mem_union_right
An element in a finite set t also belongs to the union s ∪ t.

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_small_cut    (α : 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)))    (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) :    ∃ s : Fin 4 → Finset α, (∀ i, digraph_directed_cycle_on D (s i)) ∧      Pairwise (fun i j => Disjoint (s i) (s j)) := by  have hBdeg : ∀ b ∈ B, 5 ≤ (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⟩ := hthree 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 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