AFTD Auto-Formalizing Theoretical Domains

digraph_125_four_cycles_under_extremal_and_cycle_criteria

theoremverified

A loopless oriented seven-outregular digraph on 125 vertices with dominated arcs and a cycle in every in-neighborhood contains four vertex-disjoint directed cycles, assuming the displayed induced one-, robust two-, and three-cycle criteria and the two stated clique-free three-coloring criteria.

Statement

theorem digraph_125_four_cycles_under_extremal_and_cycle_criteria
    (D : Digraph (Fin 125)) [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 → ∃ p, D.Adj p u ∧ D.Adj p v)
    (hin : ∀ v, ∃ C : Finset (Fin 125), digraph_directed_cycle_on D C ∧ ∀ w ∈ C, D.Adj w v)
    (hone : ∀ T : Finset (Fin 125), T.Nonempty →
      (∀ v ∈ T, 1 ≤ (T.filter fun w => D.Adj v w).card) →
      ∃ C : Finset (Fin 125), C ⊆ T ∧ digraph_directed_cycle_on D C)
    (htwo : ∀ T : Finset (Fin 125), 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 < 3).card ≤ 2 →
      ∃ c : Fin 2 → Finset (Fin 125), (∀ i, c i ⊆ T ∧ digraph_directed_cycle_on D (c i)) ∧
        Pairwise (fun i j => Disjoint (c i) (c j)))
    (hthree : ∀ T : Finset (Fin 125), T.Nonempty →
      (∀ v ∈ T, 5 ≤ (T.filter fun w => D.Adj v w).card) →
      ∃ c : Fin 3 → Finset (Fin 125), (∀ i, c i ⊆ T ∧ digraph_directed_cycle_on D (c i)) ∧
        Pairwise (fun i j => Disjoint (c i) (c j)))
    (hnear125 : ∀ (G : SimpleGraph (Fin 125)) [DecidableRel G.Adj],
      G.CliqueFree 4 → 5169 ≤ G.edgeFinset.card → G.Colorable 3)
    (hnear124 : ∀ (α : Type) [Fintype α] [DecidableEq α] (H : SimpleGraph α)
      [DecidableRel H.Adj], Fintype.card α = 124 → H.CliqueFree 4 →
      5086 ≤ H.edgeFinset.card → H.Colorable 3) :
    ∃ c : Fin 4 → Finset (Fin 125), (∀ i, digraph_directed_cycle_on D (c i)) ∧
      Pairwise (fun i j => Disjoint (c i) (c j))
Source
Order-125 partial result for OP-110, conditional on the cycle criteria in https://iti.mff.cuni.cz/series/2007/339.pdf and the near-extremal coloring criterion in https://arxiv.org/abs/1409.8665, Theorem 1.1.
Verified
14 Nov 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 11

The proof, explained

We argue by contradiction, assuming that the 7-out-regular oriented digraph D on 125 vertices contains no four pairwise vertex-disjoint directed cycles. Under this assumption, the common predecessor graph J has independence number at most three and a non-3-colorable complement, forcing the existence of a high-degree vertex x (deg_J(x) ≥ 46) whose removal leaves a 3-colorable complement, partitioning V \ {x} into three cliques in J. Recoloring x to the majority color class in its open neighborhood produces a 3-coloring of V where each color class has at least 7 vertices, and dominated arcs imply D is a subgraph of J. A specialized counting bound on the neighborhood structure of x proves that the number of cross-edges between distinct color classes is at most 50, whereas a general cycle criterion requires at least 54 cross-edges for any 3-coloring with parts of size at least 7, yielding a contradiction.

  1. Adjacency in the common predecessor graph is decidable.

    For any vertices u and v, unfolding the definition of the common predecessor graph reveals an existential search over the finite vertex type, which Lean resolves as decidable via typeclass inference.

    lines 5–7

      intro u v
      unfold digraph_common_predecessor_graph
      infer_instance
  2. Assuming no four disjoint cycles exist, the common predecessor graph J has no independent set of size four, its complement is not 3-colorable, and its edge count satisfies |E(J)| ≤ 2583.

    We argue by contradiction, assuming D has no four vertex-disjoint directed cycles. Since every in-neighborhood contains a directed cycle, J has no independent set of size four (i.e., its complement is 4-clique-free). Applying the overlap window theorem shows that 42 ≤ 2625 - |E(J)| ≤ 43 and that the complement Jᶜ is not 3-colorable. Linear arithmetic (omega) then implies |E(J)| ≤ 2583 and |E(J)| ≤ 2625.

    lines 35–42

    uses digraph_common_predecessor_graph_indep_free_four, digraph_125_no_four_cycles_overlap_window

      classical
      by_contra hno
      let J := digraph_common_predecessor_graph D
      have hindep := digraph_common_predecessor_graph_indep_free_four (Fin 125) D hin hno
      have hwin := digraph_125_no_four_cycles_overlap_window D hloop hori hreg hdom hin hone htwo hthree hnear125 hno
      change (42 ≤ 2625 - J.edgeFinset.card ∧ 2625 - J.edgeFinset.card ≤ 43) ∧ ¬ Jᶜ.Colorable 3 at hwin
      have hedges : J.edgeFinset.card ≤ 2583 := by omega
      have hmax : J.edgeFinset.card ≤ 2625 := by omega
  3. There exists a vertex x of degree at least 46 in J, and the remaining vertices V \ {x} partition into three cliques in J.

    Because J has no independent set of size four and Jᶜ is not 3-colorable, J must contain a vertex x with deg_J(x) ≥ 46. Deleting x leaves a 124-vertex graph whose complement is 4-clique-free with at least 5086 edges; by the 124-vertex coloring criterion, (J - x)ᶜ is 3-colorable, yielding a 3-coloring col0 where any two distinct vertices in V \ {x} of the same color are adjacent in J.

    lines 43–44

    uses graph_125_noncolorable_complement_high_degree, graph_125_high_degree_delete_complement_coloring

      obtain ⟨x,hdegree⟩ := graph_125_noncolorable_complement_high_degree J hindep hwin.2
      obtain ⟨col0,hclique0⟩ := graph_125_high_degree_delete_complement_coloring J x hindep hedges hdegree hnear124
  4. The vertex x can be recolored to match the majority color class in its open neighborhood M, while preserving the three cliques on V \ {x}.

    Let O and I be the out- and in-neighborhoods of x in D, and let M = O ∪ I. Because D is loopless, x ∉ M. Recoloring x to the color class containing the largest number of vertices of M produces a coloring col that agrees with col0 on V \ {x} and satisfies |M| ≤ 3 * |{w ∈ M : col w = col x}|. Since all vertices other than x keep their colors from col0, the restriction of each color class to V \ {x} remains a clique in J.

    lines 45–56

    uses finset_three_color_busiest_recolor

      let O : Finset (Fin 125) := Finset.univ.filter fun w => D.Adj x w
      let I : Finset (Fin 125) := Finset.univ.filter fun w => D.Adj w x
      let M := O ∪ I
      have hnotx : x ∉ M := by simp [M,O,I,hloop]
      obtain ⟨col,hcol,hbalanced⟩ := finset_three_color_busiest_recolor (Fin 125) col0 x M hnotx
      have hclique : ∀ u v, u ≠ x → v ≠ x → col u = col v → u ≠ v → J.Adj u v := by
        intro u v hu hv heq hne
        apply hclique0 u v hu hv _ hne
        calc
          col0 u = col u := (hcol u hu).symm
          _ = col v := heq
          _ = col0 v := hcol v hv
  5. Each of the three cliques on V \ {x} has size at least 7, and the capacity bound deg_J(x) + (2625 - |E(J)|) ≤ 124 holds.

    In a 125-vertex graph with at most 2583 edges where V \ {x} partitions into three cliques, deg_J(x) + 2501 ≤ |E(J)| and each clique has at least 7 vertices. Combining deg_J(x) + 2501 ≤ |E(J)| with |E(J)| ≤ 2583 via linear arithmetic establishes the capacity bound deg_J(x) + (2625 - |E(J)|) ≤ 124.

    lines 57–58

    uses graph_125_three_cliques_except_vertex_bounds

      have ⟨hcapacity,hsizes⟩ := graph_125_three_cliques_except_vertex_bounds J x col hclique hedges
      have hcap : J.degree x + (2625 - J.edgeFinset.card) ≤ 124 := by omega
  6. The digraph D is a subgraph of the common predecessor graph J.

    For every directed arc u → v in D, looplessness gives u ≠ v. The dominated arcs hypothesis ensures there is a common predecessor p such that p → u and p → v, which fulfills the definition of adjacency between u and v in J.

    lines 59–66

      have hsub : ∀ u v, D.Adj u v → J.Adj u v := by
        intro u v huv
        have hne : u ≠ v := by
          intro h
          subst v
          exact hloop u huv
        change u ≠ v ∧ ∃ p, D.Adj p u ∧ D.Adj p v
        exact ⟨hne,hdom u v huv⟩
  7. The in-degree of x satisfies 6 * d⁻(x) ≤ deg_J(x) + (2625 - |E(J)|).

    The vertex incidence bound for 7-out-regular digraphs gives (7 - 1) * d⁻(x) + |E(J)| ≤ deg_J(x) + 125 * choose(7, 2). Computing choose(7, 2) = 21 and 125 * 21 = 2625 and rearranging via linear arithmetic yields the bound.

    lines 67–71

    uses digraph_common_predecessor_vertex_incidence_bound

      have hbound : 6 * I.card ≤ J.degree x + (2625 - J.edgeFinset.card) := by
        have h := digraph_common_predecessor_vertex_incidence_bound (Fin 125) D 7 hreg x
        norm_num [Nat.choose] at h
        change 6 * I.card + J.edgeFinset.card ≤ J.degree x + 2625 at h
        omega
  8. The open neighborhood of x has size d⁻(x) + 7, and the neighborhood balance inequality d⁻(x) + 7 ≤ 3 * |{w : col w = col x ∧ (D.Adj x w ∨ D.Adj w x)}| holds.

    Because D is oriented, O and I are disjoint. With |O| = 7 by 7-out-regularity, |M| = |I| + 7. Rewriting the intersection of M with the color class of x and substituting into the recoloring bound gives the balanced neighborhood inequality.

    lines 72–88

    uses Finset.disjoint_left.mpr, Finset.card_union_of_disjoint

      have hdOI : Disjoint O I := by
        apply Finset.disjoint_left.mpr
        intro v hv1 hv2
        exact hori x v (Finset.mem_filter.mp hv1).2 (Finset.mem_filter.mp hv2).2
      have hMcard : M.card = I.card + 7 := by
        rw [Finset.card_union_of_disjoint hdOI]
        have hh : O.card = 7 := hreg x
        omega
      have hfilter : M.filter (fun w => col w = col x) =
          Finset.univ.filter (fun w => col w = col x ∧ (D.Adj x w ∨ D.Adj w x)) := by
        ext w
        simp only [M,O,I,Finset.mem_filter,Finset.mem_union,Finset.mem_univ,true_and]
        exact and_comm
      have hb : (Finset.univ.filter fun w => D.Adj w x).card + 7 ≤
          3 * (Finset.univ.filter fun w => col w = col x ∧ (D.Adj x w ∨ D.Adj w x)).card := by
        rw [← hfilter, ← hMcard]
        exact hbalanced
  9. The total number of cross-edges between different color classes in D is at most 50.

    With all structural hypotheses verified—the three cliques on V \ {x}, the inclusion D ⊆ J, orientation, 7-out-regularity, edge bounds, high degree of x, the window 42 ≤ 2625 - |E(J)| ≤ 43, the in-degree bound, capacity bound, and neighborhood balance—the exceptional cross-bound lemma proves that the sum of outgoing cross-edges across all vertices is at most 50.

    line 89

    uses graph_125_exceptional_three_clique_cross_bound

      have hcross := graph_125_exceptional_three_clique_cross_bound J D x col hclique hsub hori (hreg x) hmax hdegree hwin.1 hbound hcap hb
  10. The number of cross-edges must also be at least 54, producing a contradiction.

    Since each of the three color classes on V \ {x} contains at least 7 vertices, every color class in V has cardinality at least 7. Under the assumption of no four disjoint cycles and the cycle criteria, any 3-coloring with parts of size at least 7 must contain at least 54 cross-edges. The two bounds 54 ≤ cross and cross ≤ 50 contradict each other, and omega finishes the proof.

    lines 90–98

    uses le_trans, Finset.card_le_card, digraph_three_large_parts_no_four_cycles_cross_ge_fifty_four

      have hsize : ∀ i, 7 ≤ (Finset.univ.filter fun v => col v = i).card := by
        intro i
        apply le_trans (hsizes i)
        apply Finset.card_le_card
        intro v hv
        exact Finset.mem_filter.mpr ⟨Finset.mem_univ _,(Finset.mem_filter.mp hv).2.2⟩
      have h54 := digraph_three_large_parts_no_four_cycles_cross_ge_fifty_four (Fin 125) D col
        hsize (by intro v; rw [hreg v]) hone htwo hthree hno
      omega
digraph_common_predecessor_graph_indep_free_four
In any digraph where every in-neighborhood contains a directed cycle, if there are no four pairwise vertex-disjoint directed cycles, then the common predecessor graph has no independent set of size four.
digraph_125_no_four_cycles_overlap_window
For an oriented, 7-out-regular digraph on 125 vertices with dominated arcs satisfying the cycle criteria and having no four disjoint directed cycles, the edge count of the common predecessor graph J satisfies 42 ≤ 2625 - |E(J)| ≤ 43, and the complement graph of J is not 3-colorable.
graph_125_noncolorable_complement_high_degree
A graph on 125 vertices with no independent set of size four whose complement is not 3-colorable contains a vertex of degree at least 46.
graph_125_high_degree_delete_complement_coloring
In a graph on 125 vertices with no independent set of size four and at most 2583 edges, deleting a vertex of degree at least 46 yields a graph on 124 vertices whose complement is 3-colorable (by the 124-vertex coloring criterion), so the remaining vertices partition into three cliques.
finset_three_color_busiest_recolor
Given a 3-coloring of a finite type and a vertex x outside a subset M, x can be recolored so that its color class contains at least one third of the elements of M, without changing the colors of any other vertices.
graph_125_three_cliques_except_vertex_bounds
If the vertices other than x in a graph on 125 vertices with at most 2583 edges partition into three cliques, then deg(x) + 2501 ≤ |E(G)| and each of the three cliques contains at least 7 vertices.
digraph_common_predecessor_vertex_incidence_bound
In an r-out-regular digraph, the in-degree of any vertex v and the edge count of the common predecessor graph J satisfy (r - 1) * d⁻(v) + |E(J)| ≤ deg_J(v) + |V| * choose(r, 2).
Finset.disjoint_left.mpr
Two finite sets are disjoint if no element of the first set is an element of the second set.
Finset.card_union_of_disjoint
The cardinality of the union of two disjoint finite sets is the sum of their cardinalities.
graph_125_exceptional_three_clique_cross_bound
Under the structural bounds on edge count, degrees, capacity, and neighborhood balance for a vertex x with three cliques on V \ {x}, the total number of cross-edges of D between different color classes is at most 50.
le_trans
If a ≤ b and b ≤ c in a preordered type, then a ≤ c.
Finset.card_le_card
If a finite set s is a subset of a finite set t, then |s| ≤ |t|.
digraph_three_large_parts_no_four_cycles_cross_ge_fifty_four
In any digraph with minimum out-degree at least 7 satisfying the cycle criteria and having no four vertex-disjoint directed cycles, any 3-coloring where each color class has at least 7 vertices must have at least 54 cross-edges.

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

set_option maxHeartbeats 4000000set_option maxRecDepth 4096private instance in833_order125_final_decAdj {α : Type} [Fintype α] [DecidableEq α] (D : Digraph α)    [DecidableRel D.Adj] : DecidableRel (digraph_common_predecessor_graph D).Adj := by  intro u v  unfold digraph_common_predecessor_graph  infer_instancetheorem digraph_125_four_cycles_under_extremal_and_cycle_criteria    (D : Digraph (Fin 125)) [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 → ∃ p, D.Adj p u ∧ D.Adj p v)    (hin : ∀ v, ∃ C : Finset (Fin 125), digraph_directed_cycle_on D C ∧ ∀ w ∈ C, D.Adj w v)    (hone : ∀ T : Finset (Fin 125), T.Nonempty →      (∀ v ∈ T, 1 ≤ (T.filter fun w => D.Adj v w).card) →      ∃ C : Finset (Fin 125), C ⊆ T ∧ digraph_directed_cycle_on D C)    (htwo : ∀ T : Finset (Fin 125), 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 < 3).card ≤ 2 →      ∃ c : Fin 2 → Finset (Fin 125), (∀ i, c i ⊆ T ∧ digraph_directed_cycle_on D (c i)) ∧        Pairwise (fun i j => Disjoint (c i) (c j)))    (hthree : ∀ T : Finset (Fin 125), T.Nonempty →      (∀ v ∈ T, 5 ≤ (T.filter fun w => D.Adj v w).card) →      ∃ c : Fin 3 → Finset (Fin 125), (∀ i, c i ⊆ T ∧ digraph_directed_cycle_on D (c i)) ∧        Pairwise (fun i j => Disjoint (c i) (c j)))    (hnear125 : ∀ (G : SimpleGraph (Fin 125)) [DecidableRel G.Adj],      G.CliqueFree 4 → 5169 ≤ G.edgeFinset.card → G.Colorable 3)    (hnear124 : ∀ (α : Type) [Fintype α] [DecidableEq α] (H : SimpleGraph α)      [DecidableRel H.Adj], Fintype.card α = 124 → H.CliqueFree 4 →      5086 ≤ H.edgeFinset.card → H.Colorable 3) :    ∃ c : Fin 4 → Finset (Fin 125), (∀ i, digraph_directed_cycle_on D (c i)) ∧      Pairwise (fun i j => Disjoint (c i) (c j)) := by  classical  by_contra hno  let J := digraph_common_predecessor_graph D  have hindep := digraph_common_predecessor_graph_indep_free_four (Fin 125) D hin hno  have hwin := digraph_125_no_four_cycles_overlap_window D hloop hori hreg hdom hin hone htwo hthree hnear125 hno  change (42 ≤ 2625 - J.edgeFinset.card ∧ 2625 - J.edgeFinset.card ≤ 43) ∧ ¬ Jᶜ.Colorable 3 at hwin  have hedges : J.edgeFinset.card ≤ 2583 := by omega  have hmax : J.edgeFinset.card ≤ 2625 := by omega  obtain ⟨x,hdegree⟩ := graph_125_noncolorable_complement_high_degree J hindep hwin.2  obtain ⟨col0,hclique0⟩ := graph_125_high_degree_delete_complement_coloring J x hindep hedges hdegree hnear124  let O : Finset (Fin 125) := Finset.univ.filter fun w => D.Adj x w  let I : Finset (Fin 125) := Finset.univ.filter fun w => D.Adj w x  let M := O ∪ I  have hnotx : x ∉ M := by simp [M,O,I,hloop]  obtain ⟨col,hcol,hbalanced⟩ := finset_three_color_busiest_recolor (Fin 125) col0 x M hnotx  have hclique : ∀ u v, u ≠ x → v ≠ x → col u = col v → u ≠ v → J.Adj u v := by    intro u v hu hv heq hne    apply hclique0 u v hu hv _ hne    calc      col0 u = col u := (hcol u hu).symm      _ = col v := heq      _ = col0 v := hcol v hv  have ⟨hcapacity,hsizes⟩ := graph_125_three_cliques_except_vertex_bounds J x col hclique hedges  have hcap : J.degree x + (2625 - J.edgeFinset.card) ≤ 124 := by omega  have hsub : ∀ u v, D.Adj u v → J.Adj u v := by    intro u v huv    have hne : u ≠ v := by      intro h      subst v      exact hloop u huv    change u ≠ v ∧ ∃ p, D.Adj p u ∧ D.Adj p v    exact ⟨hne,hdom u v huv⟩  have hbound : 6 * I.card ≤ J.degree x + (2625 - J.edgeFinset.card) := by    have h := digraph_common_predecessor_vertex_incidence_bound (Fin 125) D 7 hreg x    norm_num [Nat.choose] at h    change 6 * I.card + J.edgeFinset.card ≤ J.degree x + 2625 at h    omega  have hdOI : Disjoint O I := by    apply Finset.disjoint_left.mpr    intro v hv1 hv2    exact hori x v (Finset.mem_filter.mp hv1).2 (Finset.mem_filter.mp hv2).2  have hMcard : M.card = I.card + 7 := by    rw [Finset.card_union_of_disjoint hdOI]    have hh : O.card = 7 := hreg x    omega  have hfilter : M.filter (fun w => col w = col x) =      Finset.univ.filter (fun w => col w = col x ∧ (D.Adj x w ∨ D.Adj w x)) := by    ext w    simp only [M,O,I,Finset.mem_filter,Finset.mem_union,Finset.mem_univ,true_and]    exact and_comm  have hb : (Finset.univ.filter fun w => D.Adj w x).card + 7 ≤      3 * (Finset.univ.filter fun w => col w = col x ∧ (D.Adj x w ∨ D.Adj w x)).card := by    rw [← hfilter, ← hMcard]    exact hbalanced  have hcross := graph_125_exceptional_three_clique_cross_bound J D x col hclique hsub hori (hreg x) hmax hdegree hwin.1 hbound hcap hb  have hsize : ∀ i, 7 ≤ (Finset.univ.filter fun v => col v = i).card := by    intro i    apply le_trans (hsizes i)    apply Finset.card_le_card    intro v hv    exact Finset.mem_filter.mpr ⟨Finset.mem_univ _,(Finset.mem_filter.mp hv).2.2⟩  have h54 := digraph_three_large_parts_no_four_cycles_cross_ge_fifty_four (Fin 125) D col    hsize (by intro v; rw [hreg v]) hone htwo hthree hno  omega
See it in the graphDiscuss this resultChallenge it