AFTD Auto-Formalizing Theoretical Domains

digraph_127_four_cycles_under_extremal_and_cycle_criteria

theoremverified

A 7-outregular oriented digraph on 127 vertices with dominated arcs and a cycle in every in-neighborhood contains four disjoint directed cycles, assuming the displayed induced one-, two- and three-cycle criteria and the near-extremal clique-free coloring criterion.

Statement

theorem digraph_127_four_cycles_under_extremal_and_cycle_criteria
    (D : Digraph (Fin 127)) [DecidableRel D.Adj]
    (hloop : ∀ v, ¬ D.Adj v v)
    (hori : ∀ u v, D.Adj u v → ¬ D.Adj v u)
    (hreg : ∀ v, (Finset.univ.filter fun w => D.Adj v w).card = 7)
    (hdom : ∀ u v, D.Adj u v → ∃ w, D.Adj w u ∧ D.Adj w v)
    (hin : ∀ v, ∃ C : Finset (Fin 127), digraph_directed_cycle_on D C ∧
      ∀ w ∈ C, D.Adj w v)
    (hone : ∀ T : Finset (Fin 127), T.Nonempty →
      (∀ v ∈ T, 1 ≤ (T.filter fun w => D.Adj v w).card) →
      ∃ C : Finset (Fin 127), C ⊆ T ∧ digraph_directed_cycle_on D C)
    (htwo : ∀ T : Finset (Fin 127), T.Nonempty →
      (∀ v ∈ T, 3 ≤ (T.filter fun w => D.Adj v w).card) →
      ∃ c : Fin 2 → Finset (Fin 127), (∀ i, c i ⊆ T ∧ digraph_directed_cycle_on D (c i)) ∧
        Pairwise (fun i j => Disjoint (c i) (c j)))
    (hthree : ∀ T : Finset (Fin 127), T.Nonempty →
      (∀ v ∈ T, 5 ≤ (T.filter fun w => D.Adj v w).card) →
      ∃ c : Fin 3 → Finset (Fin 127), (∀ i, c i ⊆ T ∧ digraph_directed_cycle_on D (c i)) ∧
        Pairwise (fun i j => Disjoint (c i) (c j)))
    (hnear : ∀ (n s : ℕ), 2 ≤ s → 2 * s + 1 ≤ n →
      ∀ (G : SimpleGraph (Fin n)) [DecidableRel G.Adj],
        G.CliqueFree (s + 1) →
        (SimpleGraph.turanGraph n s).edgeFinset.card + 2 ≤ G.edgeFinset.card + n / s →
        G.Colorable s) :
    ∃ c : Fin 4 → Finset (Fin 127), (∀ i, digraph_directed_cycle_on D (c i)) ∧
      Pairwise (fun i j => Disjoint (c i) (c j))
Source
Proposed exceptional-vertex reduction for OP-110; experiments 12602 and 12603 check the finite arithmetic.
Verified
03 Nov 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 6

The proof, explained

The proof argues by contradiction: suppose D does not contain four pairwise disjoint directed cycles. Since every in-neighborhood contains a cycle, this implies that the common predecessor graph of D contains no independent set of size 4. For a 7-outregular digraph on 127 vertices, this independence condition forces the overlap defect to be strictly less than 127. Applying the cycle packing step with k = 3 and d = 5 lifts the 3-cycle packing hypothesis to produce four disjoint directed cycles, contradicting the assumption.

  1. Assume for contradiction that D has no four pairwise disjoint directed cycles.

    We apply classical reasoning and proceed by contradiction, introducing the hypothesis `hno` that there is no family of 4 pairwise disjoint directed cycles in D.

    lines 27–28

      classical
      by_contra hno
  2. The common predecessor graph of D has no independent set of size 4.

    Because every vertex has a directed cycle in its in-neighborhood (`hin`), an independent set of size 4 in the common predecessor graph would yield 4 disjoint directed cycles; hence the assumption `hno` implies the graph is 4-independent-set-free by `digraph_common_predecessor_graph_indep_free_four`.

    line 29

    uses digraph_common_predecessor_graph_indep_free_four

      have hindep := digraph_common_predecessor_graph_indep_free_four (Fin 127) D hin hno
  3. The overlap defect of D is strictly bounded by 127: 3 * (∑ v, Nat.choose (d⁺(v)) 2 - |E(G)|) < 127.

    We invoke `digraph_127_regular_independence_small_overlap`, which derives this small overlap inequality for any 7-regular digraph on 127 vertices whose common predecessor graph has independence number less than 4.

    line 30

    uses digraph_127_regular_independence_small_overlap

      have hsmall := digraph_127_regular_independence_small_overlap D hreg hindep
  4. Every vertex v in D has out-degree at least 5 + 2 = 7.

    For any vertex v, rewriting with the 7-outregularity hypothesis `hreg v` shows that 5 + 2 ≤ 7 = d⁺(v).

    lines 31–33

      have hdeg' : ∀ v, 5 + 2 ≤ (Finset.univ.filter fun w => D.Adj v w).card := by
        intro v
        rw [hreg v]
  5. D contains 4 pairwise disjoint directed cycles, contradicting hno.

    We apply the cycle packing step `digraph_small_overlap_cycle_packing_step` with parameters k = 3 and d = 5, using the loopless property, out-degree bound, arc domination, the small overlap bound, and the 3-cycle packing criterion `hthree`. This produces 4 pairwise disjoint directed cycles, contradicting `hno` and concluding the proof.

    lines 34–35

    uses digraph_small_overlap_cycle_packing_step, SimpleGraph.mem_edgeFinset

      exact hno (digraph_small_overlap_cycle_packing_step (Fin 127) D 3 5 hloop hdeg' hdom
        (by convert hsmall using 4; ext e; simp only [SimpleGraph.mem_edgeFinset]) hthree)
digraph_common_predecessor_graph_indep_free_four
If every vertex of a digraph has a directed cycle in its in-neighborhood and the digraph lacks 4 pairwise disjoint directed cycles, then its common predecessor graph has no independent set of size 4.
digraph_127_regular_independence_small_overlap
For a 7-outregular digraph on 127 vertices whose common predecessor graph has no independent set of size 4, the triple of the total overlap defect is strictly less than 127.
digraph_small_overlap_cycle_packing_step
In a loopless digraph with dominated arcs and minimum out-degree at least d + 2 satisfying the small overlap defect condition, if every induced subgraph with minimum out-degree at least d contains k disjoint directed cycles, then the digraph contains k + 1 disjoint directed cycles.
SimpleGraph.mem_edgeFinset
An edge belongs to the finite set of edges of a graph if and only if it belongs to its edge set.

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_127_four_cycles_under_extremal_and_cycle_criteria    (D : Digraph (Fin 127)) [DecidableRel D.Adj]    (hloop : ∀ v, ¬ D.Adj v v)    (hori : ∀ u v, D.Adj u v → ¬ D.Adj v u)    (hreg : ∀ v, (Finset.univ.filter fun w => D.Adj v w).card = 7)    (hdom : ∀ u v, D.Adj u v → ∃ w, D.Adj w u ∧ D.Adj w v)    (hin : ∀ v, ∃ C : Finset (Fin 127), digraph_directed_cycle_on D C ∧      ∀ w ∈ C, D.Adj w v)    (hone : ∀ T : Finset (Fin 127), T.Nonempty →      (∀ v ∈ T, 1 ≤ (T.filter fun w => D.Adj v w).card) →      ∃ C : Finset (Fin 127), C ⊆ T ∧ digraph_directed_cycle_on D C)    (htwo : ∀ T : Finset (Fin 127), T.Nonempty →      (∀ v ∈ T, 3 ≤ (T.filter fun w => D.Adj v w).card) →      ∃ c : Fin 2 → Finset (Fin 127), (∀ i, c i ⊆ T ∧ digraph_directed_cycle_on D (c i)) ∧        Pairwise (fun i j => Disjoint (c i) (c j)))    (hthree : ∀ T : Finset (Fin 127), T.Nonempty →      (∀ v ∈ T, 5 ≤ (T.filter fun w => D.Adj v w).card) →      ∃ c : Fin 3 → Finset (Fin 127), (∀ i, c i ⊆ T ∧ digraph_directed_cycle_on D (c i)) ∧        Pairwise (fun i j => Disjoint (c i) (c j)))    (hnear : ∀ (n s : ℕ), 2 ≤ s → 2 * s + 1 ≤ n →      ∀ (G : SimpleGraph (Fin n)) [DecidableRel G.Adj],        G.CliqueFree (s + 1) →        (SimpleGraph.turanGraph n s).edgeFinset.card + 2 ≤ G.edgeFinset.card + n / s →        G.Colorable s) :    ∃ c : Fin 4 → Finset (Fin 127), (∀ i, digraph_directed_cycle_on D (c i)) ∧      Pairwise (fun i j => Disjoint (c i) (c j)) := by  classical  by_contra hno  have hindep := digraph_common_predecessor_graph_indep_free_four (Fin 127) D hin hno  have hsmall := digraph_127_regular_independence_small_overlap D hreg hindep  have hdeg' : ∀ v, 5 + 2 ≤ (Finset.univ.filter fun w => D.Adj v w).card := by    intro v    rw [hreg v]  exact hno (digraph_small_overlap_cycle_packing_step (Fin 127) D 3 5 hloop hdeg' hdom    (by convert hsmall using 4; ext e; simp only [SimpleGraph.mem_edgeFinset]) hthree)
See it in the graphDiscuss this resultChallenge it