AFTD Auto-Formalizing Theoretical Domains

digraph_two_cycles_boundary_obstruction

theoremverified

If a digraph of minimum outdegree seven has no four disjoint cycles, then for any two disjoint cycles with nonempty remainder either some outside vertex has at least six out-neighbors in their union or at least three outside vertices have at least five, assuming the displayed robust two-cycle condition.

Statement

theorem digraph_two_cycles_boundary_obstruction
    (α : 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)
    (hno : ¬ ∃ s : Fin 4 → Finset α, (∀ i, digraph_directed_cycle_on D (s i)) ∧
      Pairwise (fun i j => Disjoint (s i) (s j))) :
    (∃ v ∉ (C₁ ∪ C₂), 6 ≤ ((C₁ ∪ C₂).filter fun w => D.Adj v w).card) ∨
      3 ≤ ((Finset.univ \ (C₁ ∪ C₂)).filter fun v =>
        5 ≤ ((C₁ ∪ C₂).filter fun w => D.Adj v w).card).card
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 2
  • 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…
  • digraph_four_cycles_from_two_cycles_few_badTwo disjoint directed cycles with nonempty remainder can be extended to four under the displayed robust two-cycle condition if each…

The proof, explained

The proof proceeds by contradiction. Assuming that neither boundary obstruction condition holds, every vertex outside C₁ ∪ C₂ has at most five out-neighbors in C₁ ∪ C₂, and at most two outside vertices have at least five out-neighbors in C₁ ∪ C₂. These two bounds fulfill the preconditions of `digraph_four_cycles_from_two_cycles_few_bad`, which produces four pairwise disjoint directed cycles and contradicts the assumption that no four such cycles exist.

  1. Assume, for contradiction, that neither boundary condition holds.

    We use classical logic and assume the negation of the disjunction: there is no outside vertex with at least 6 out-neighbors in C₁ ∪ C₂, and the number of outside vertices with at least 5 out-neighbors in C₁ ∪ C₂ is strictly less than 3.

    lines 18–19

      classical
      by_contra h
  2. Every outside vertex has at most 5 out-neighbors in C₁ ∪ C₂.

    For any vertex v ∉ C₁ ∪ C₂, if its out-degree into C₁ ∪ C₂ were not at most 5, it would have at least 6 out-neighbors in C₁ ∪ C₂ by basic integer arithmetic. This would witness the first branch of the conclusion disjunction, contradicting our assumption h.

    lines 20–25

      have hnoall : ∀ v ∉ (C₁ ∪ C₂), ((C₁ ∪ C₂).filter fun w => D.Adj v w).card ≤ 5 := by
        intro v hv
        by_contra hh
        apply h
        left
        exact ⟨v, hv, by omega⟩
  3. At most 2 outside vertices have at least 5 out-neighbors in C₁ ∪ C₂.

    If the number of vertices in the complement with at least 5 out-neighbors in C₁ ∪ C₂ were not at most 2, it would be at least 3 by basic integer arithmetic. This would satisfy the second branch of the conclusion disjunction, contradicting our assumption h.

    lines 26–31

      have hfew : ((Finset.univ \ (C₁ ∪ C₂)).filter fun v =>
          5 ≤ ((C₁ ∪ C₂).filter fun w => D.Adj v w).card).card ≤ 2 := by
        by_contra hh
        apply h
        right
        omega
  4. The assumption leads to a contradiction, concluding the proof.

    With the upper bound of 5 out-neighbors for all outside vertices and at most 2 vertices reaching 5, lemma `digraph_four_cycles_from_two_cycles_few_bad` guarantees that the digraph contains 4 pairwise disjoint directed cycles. This directly contradicts the hypothesis hno that no 4 pairwise disjoint directed cycles exist.

    line 32

    uses digraph_four_cycles_from_two_cycles_few_bad

      exact hno (digraph_four_cycles_from_two_cycles_few_bad α D hloop hdeg hrobust C₁ C₂ hC₁ hC₂ hdis hTne hnoall hfew)
digraph_four_cycles_from_two_cycles_few_bad
Under the given hypotheses (minimum outdegree at least 7, no loops, robust two-cycle condition), if there are two disjoint directed cycles whose complement is nonempty, every vertex outside has at most 5 out-neighbors in their union, and at most 2 outside vertices have at least 5 out-neighbors in their union, then the digraph contains 4 pairwise disjoint directed cycles.

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_two_cycles_boundary_obstruction    (α : 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)    (hno : ¬ ∃ s : Fin 4 → Finset α, (∀ i, digraph_directed_cycle_on D (s i)) ∧      Pairwise (fun i j => Disjoint (s i) (s j))) :    (∃ v ∉ (C₁ ∪ C₂), 6 ≤ ((C₁ ∪ C₂).filter fun w => D.Adj v w).card) ∨      3 ≤ ((Finset.univ \ (C₁ ∪ C₂)).filter fun v =>        5 ≤ ((C₁ ∪ C₂).filter fun w => D.Adj v w).card).card := by  classical  by_contra h  have hnoall : ∀ v ∉ (C₁ ∪ C₂), ((C₁ ∪ C₂).filter fun w => D.Adj v w).card ≤ 5 := by    intro v hv    by_contra hh    apply h    left    exact ⟨v, hv, by omega⟩  have hfew : ((Finset.univ \ (C₁ ∪ C₂)).filter fun v =>      5 ≤ ((C₁ ∪ C₂).filter fun w => D.Adj v w).card).card ≤ 2 := by    by_contra hh    apply h    right    omega  exact hno (digraph_four_cycles_from_two_cycles_few_bad α D hloop hdeg hrobust C₁ C₂ hC₁ hC₂ hdis hTne hnoall hfew)
See it in the graphDiscuss this resultChallenge it