AFTD Auto-Formalizing Theoretical Domains

digraph_125_no_four_cycles_overlap_window

theoremverified

For a loopless oriented seven-outregular digraph on 125 vertices with dominated arcs, a cycle in each in-neighborhood, and no four disjoint cycles, the common-predecessor overlap is 42 or 43 and its complement is not three-colorable, assuming the displayed induced one-, robust two-, and three-cycle criteria and the stated near-extremal coloring criterion.

Statement

theorem digraph_125_no_four_cycles_overlap_window
    (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)))
    (hnear : ∀ (G : SimpleGraph (Fin 125)) [DecidableRel G.Adj],
      G.CliqueFree 4 → 5169 ≤ G.edgeFinset.card → G.Colorable 3)
    (hno : ¬ ∃ c : Fin 4 → Finset (Fin 125), (∀ i, digraph_directed_cycle_on D (c i)) ∧
      Pairwise (fun i j => Disjoint (c i) (c j)))
 :
    let J := digraph_common_predecessor_graph D
    (42 ≤ 2625 - J.edgeFinset.card ∧ 2625 - J.edgeFinset.card ≤ 43) ∧ ¬ Jᶜ.Colorable 3
Source
Overlap-window reduction for OP-110, using the cycle criteria in https://iti.mff.cuni.cz/series/2007/339.pdf and the coloring criterion in https://arxiv.org/abs/1409.8665, Theorem 1.1.
Verified
14 Nov 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 7
Used by 1

The proof, explained

The proof establishes that the common-predecessor graph J has no independent set of size 4, so its complement H = Jᶜ is K₄-free. If the common-predecessor overlap 2625 - |E(J)| were less than 125 / 3 ≈ 41.67, cycle packing would produce 4 disjoint directed cycles in D, contradicting the no-four-cycles hypothesis; this bounds |E(J)| ≤ 2583 and gives the lower bound 42 on the overlap. A hypothetical 3-coloring of H would partition J into 3 cliques, but cross-arc bounds for 3-clique partitions force at most 41 cross-arcs, contradicting the structural lower bound of 54 cross-arcs for digraphs without 4 disjoint cycles. Because H is K₄-free and not 3-colorable, the near-extremal coloring criterion bounds |E(H)| ≤ 5168, which combines with the total edge count |E(J)| + |E(H)| = 7750 to yield the upper bound 43 on the overlap.

  1. Adjacency in the common-predecessor graph of D is decidable.

    For any two vertices u and v, the condition that u ≠ v and there exists a common predecessor p with arcs p → u and p → v is decidable because the vertex set is finite and adjacency in D is decidable.

    lines 3–7

    private instance in833_common_predecessor_decidable125 {α : 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_instance
  2. The common-predecessor graph J has no independent set of size 4, so its complement H = Jᶜ contains no 4-clique (H is K₄-free).

    Let J be the common-predecessor graph of D and H its complement. By digraph_common_predecessor_graph_indep_free_four, since every vertex has a directed cycle in its in-neighborhood and D has no four disjoint directed cycles, J has no independent set of size 4. Translating to the complement graph, an independent set in J is a clique in H, so H is K₄-free.

    lines 35–39

    uses digraph_common_predecessor_graph_indep_free_four

      classical
      let J := digraph_common_predecessor_graph D
      let H := Jᶜ
      have hindep := digraph_common_predecessor_graph_indep_free_four (Fin 125) D hin hno
      have hfree : H.CliqueFree 4 := by simpa [H,J] using hindep
  3. The sum of out-degree binomial coefficients is 2625, and every vertex has out-degree at least 5 + 2.

    Since D is 7-outregular, each vertex contributes 7 choose 2 = 21 pairs of out-neighbors. Across all 125 vertices, the sum of these binomial coefficients is 125 * 21 = 2625. Furthermore, 7 ≥ 5 + 2, satisfying the degree requirement for cycle packing.

    lines 40–45

      have hinc : (∑ v : Fin 125, Nat.choose (Finset.univ.filter fun w => D.Adj v w).card 2) = 2625 := by
        simp [hreg]
        norm_num [Nat.choose]
      have hdeg' : ∀ v, 5 + 2 ≤ (Finset.univ.filter fun w => D.Adj v w).card := by
        intro v
        rw [hreg v]
  4. The common-predecessor overlap satisfies 125 ≤ 3 * (2625 - |E(J)|), which implies |E(J)| ≤ 2583.

    Suppose for contradiction that 3 * (2625 - |E(J)|) < 125. By digraph_small_overlap_cycle_packing_step with k = 3 and d = 5, the 7-regularity, looplessness, arc domination, and the 3-cycle packing condition would guarantee the existence of 3 + 1 = 4 pairwise disjoint directed cycles, contradicting the hypothesis that D has no four disjoint cycles. Thus 125 ≤ 3 * (2625 - |E(J)|), from which integer arithmetic yields |E(J)| ≤ 2583.

    lines 46–54

    uses Fintype.card_fin, digraph_small_overlap_cycle_packing_step, SimpleGraph.mem_edgeFinset

      have hz : 125 ≤ 3 * (2625 - J.edgeFinset.card) := by
        by_contra hh
        have hs : 3 * ((∑ v : Fin 125, Nat.choose (Finset.univ.filter fun w => D.Adj v w).card 2) -
          J.edgeFinset.card) < Fintype.card (Fin 125) := by rw [hinc]; simp only [Fintype.card_fin]; omega
        apply hno
        apply digraph_small_overlap_cycle_packing_step (Fin 125) D 3 5 hloop hdeg' hdom
        · convert hs using 4 <;> ext e <;> simp only [SimpleGraph.mem_edgeFinset] <;> rfl
        · exact hthree
      have hedges : J.edgeFinset.card ≤ 2583 := by omega
  5. Every directed arc of D is an edge in the common-predecessor graph J.

    For any arc u → v in D, the vertices u and v are distinct because D is loopless, and they share a common predecessor by the arc domination hypothesis. Therefore, u and v are adjacent in J.

    lines 55–62

      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⟩
  6. The complement graph H = Jᶜ is not 3-colorable.

    Suppose for contradiction that H has a proper 3-coloring. Two distinct vertices of the same color cannot be adjacent in H, so they must be adjacent in J; thus each color class induces a clique in J. By graph_125_three_clique_partition_oriented_cross_bound, because |E(J)| ≤ 2583 and D is an oriented subgraph of J, every color class must have size at least 7, and the number of cross-arcs between different color classes is at most 41. However, digraph_three_large_parts_no_four_cycles_cross_ge_fifty_four shows that any 3-partition into parts of size at least 7 must have at least 54 cross-arcs. This contradiction (54 ≤ cross-arcs ≤ 41) proves H is not 3-colorable.

    lines 63–74

    uses SimpleGraph.compl_adj, graph_125_three_clique_partition_oriented_cross_bound, digraph_three_large_parts_no_four_cycles_cross_ge_fifty_four

      have hnotcolor : ¬ H.Colorable 3 := by
        intro hc
        obtain ⟨col⟩ := hc
        have hclique : ∀ u v, col u = col v → u ≠ v → J.Adj u v := by
          intro u v heq hne
          by_contra h
          have hadj : H.Adj u v := by simp [H, SimpleGraph.compl_adj, hne, h]
          exact (col.map_rel hadj) heq
        have hb := graph_125_three_clique_partition_oriented_cross_bound J D col hclique hsub hori hedges
        have hc := digraph_three_large_parts_no_four_cycles_cross_ge_fifty_four (Fin 125) D col
          hb.1 (by intro v; rw [hreg v]) hone htwo hthree hno
        omega
  7. The total number of edges in J and H combined is 7750.

    Because H is the complement of J, their edge sets are disjoint and their union is the edge set of the complete graph on 125 vertices. The number of edges in the complete graph is 125 choose 2 = 125 * 124 / 2 = 7750. Thus |E(J)| + |E(H)| = 7750.

    lines 75–86

    uses SimpleGraph.disjoint_edgeFinset, disjoint_compl_right, SimpleGraph.edgeFinset_sup, SimpleGraph.edgeFinset_inj.mpr, sup_compl_eq_top, Finset.card_union_of_disjoint, SimpleGraph.card_edgeFinset_top_eq_card_choose_two, Nat.choose_two_right

      have hdis : Disjoint J.edgeFinset H.edgeFinset := by
        rw [SimpleGraph.disjoint_edgeFinset]
        change Disjoint J Jᶜ
        exact disjoint_compl_right
      have hunion : J.edgeFinset ∪ H.edgeFinset = (⊤ : SimpleGraph (Fin 125)).edgeFinset := by
        rw [← SimpleGraph.edgeFinset_sup]
        change (J ⊔ Jᶜ).edgeFinset = _
        exact SimpleGraph.edgeFinset_inj.mpr sup_compl_eq_top
      have htotal : J.edgeFinset.card + H.edgeFinset.card = 7750 := by
        rw [← Finset.card_union_of_disjoint hdis, hunion, SimpleGraph.card_edgeFinset_top_eq_card_choose_two]
        rw [Nat.choose_two_right]
        norm_num
  8. The complement graph H has at most 5168 edges.

    If |E(H)| were at least 5169, then since H is K₄-free, the near-extremal coloring criterion would imply that H is 3-colorable. But H was already shown not to be 3-colorable, so |E(H)| ≤ 5168.

    lines 87–89

      have hupper : H.edgeFinset.card ≤ 5168 := by
        by_contra hh
        exact hnotcolor (hnear H hfree (by omega))
  9. The common-predecessor overlap 2625 - |E(J)| is 42 or 43, and H is not 3-colorable. automation

    From |E(J)| ≤ 2583, the overlap satisfies 2625 - |E(J)| ≥ 2625 - 2583 = 42. From |E(J)| + |E(H)| = 7750 and |E(H)| ≤ 5168, we have |E(J)| ≥ 7750 - 5168 = 2582, so 2625 - |E(J)| ≤ 2625 - 2582 = 43. Linear arithmetic confirms 42 ≤ 2625 - |E(J)| ≤ 43, and non-3-colorability of H was established earlier.

    lines 90–91

      change (42 ≤ 2625 - J.edgeFinset.card ∧ 2625 - J.edgeFinset.card ≤ 43) ∧ ¬ H.Colorable 3
      exact ⟨⟨by omega, by omega⟩, hnotcolor⟩
Fintype.card_fin
The cardinality of the standard finite type Fin n is n.
Finset.card_union_of_disjoint
The cardinality of the union of two disjoint finite sets is the sum of their cardinalities.
Nat.choose_two_right
For any natural number n, n choose 2 equals n * (n - 1) / 2.
SimpleGraph.compl_adj
Two vertices are adjacent in the complement graph if and only if they are distinct and not adjacent in the original graph.
SimpleGraph.edgeFinset_sup
The edge Finset of the supremum (join) of two graphs is the union of their edge Finsets.
SimpleGraph.edgeFinset_inj.mpr
If two simple graphs are equal, their edge Finsets are equal.
SimpleGraph.disjoint_edgeFinset
Two graphs have disjoint edge Finsets if and only if the graphs themselves are disjoint.
SimpleGraph.mem_edgeFinset
An unordered pair is in the edge Finset of a graph if and only if it belongs to its edge set.
SimpleGraph.card_edgeFinset_top_eq_card_choose_two
The number of edges in the complete graph on a vertex set V is |V| choose 2.
digraph_common_predecessor_graph_indep_free_four
If every vertex of a digraph has a directed cycle in its in-neighborhood and the digraph has no four disjoint directed cycles, then its common-predecessor graph has no independent set of size four.
digraph_small_overlap_cycle_packing_step
In a loopless digraph with dominated arcs, if the minimum out-degree is at least d + 2 and the common-predecessor overlap satisfies 3 * overlap < |V|, then any k-cycle packing property for minimum out-degree d extends to packing k + 1 pairwise disjoint cycles.
digraph_three_large_parts_no_four_cycles_cross_ge_fifty_four
In an out-regular digraph partitioned into three parts of size at least 7 with no four disjoint cycles and satisfying the 1-, 2-, and 3-cycle packing conditions, there are at least 54 cross-arcs between different parts.
disjoint_compl_right
Any element in a Heyting or Boolean algebra is disjoint from its complement.
graph_125_three_clique_partition_oriented_cross_bound
If the common-predecessor graph on 125 vertices has at most 2583 edges and is partitioned into three cliques containing an oriented subgraph, each clique has size at least 7 and there are at most 41 cross-edges.
sup_compl_eq_top
The join of an element with its complement is the top element (the complete graph).

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 5000000set_option maxRecDepth 4096private instance in833_common_predecessor_decidable125 {α : 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_no_four_cycles_overlap_window    (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)))    (hnear : ∀ (G : SimpleGraph (Fin 125)) [DecidableRel G.Adj],      G.CliqueFree 4 → 5169 ≤ G.edgeFinset.card → G.Colorable 3)    (hno : ¬ ∃ c : Fin 4 → Finset (Fin 125), (∀ i, digraph_directed_cycle_on D (c i)) ∧      Pairwise (fun i j => Disjoint (c i) (c j))) :    let J := digraph_common_predecessor_graph D    (42 ≤ 2625 - J.edgeFinset.card ∧ 2625 - J.edgeFinset.card ≤ 43) ∧ ¬ Jᶜ.Colorable 3 := by  classical  let J := digraph_common_predecessor_graph D  let H := Jᶜ  have hindep := digraph_common_predecessor_graph_indep_free_four (Fin 125) D hin hno  have hfree : H.CliqueFree 4 := by simpa [H,J] using hindep  have hinc : (∑ v : Fin 125, Nat.choose (Finset.univ.filter fun w => D.Adj v w).card 2) = 2625 := by    simp [hreg]    norm_num [Nat.choose]  have hdeg' : ∀ v, 5 + 2 ≤ (Finset.univ.filter fun w => D.Adj v w).card := by    intro v    rw [hreg v]  have hz : 125 ≤ 3 * (2625 - J.edgeFinset.card) := by    by_contra hh    have hs : 3 * ((∑ v : Fin 125, Nat.choose (Finset.univ.filter fun w => D.Adj v w).card 2) -      J.edgeFinset.card) < Fintype.card (Fin 125) := by rw [hinc]; simp only [Fintype.card_fin]; omega    apply hno    apply digraph_small_overlap_cycle_packing_step (Fin 125) D 3 5 hloop hdeg' hdom    · convert hs using 4 <;> ext e <;> simp only [SimpleGraph.mem_edgeFinset] <;> rfl    · exact hthree  have hedges : J.edgeFinset.card ≤ 2583 := 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 hnotcolor : ¬ H.Colorable 3 := by    intro hc    obtain ⟨col⟩ := hc    have hclique : ∀ u v, col u = col v → u ≠ v → J.Adj u v := by      intro u v heq hne      by_contra h      have hadj : H.Adj u v := by simp [H, SimpleGraph.compl_adj, hne, h]      exact (col.map_rel hadj) heq    have hb := graph_125_three_clique_partition_oriented_cross_bound J D col hclique hsub hori hedges    have hc := digraph_three_large_parts_no_four_cycles_cross_ge_fifty_four (Fin 125) D col      hb.1 (by intro v; rw [hreg v]) hone htwo hthree hno    omega  have hdis : Disjoint J.edgeFinset H.edgeFinset := by    rw [SimpleGraph.disjoint_edgeFinset]    change Disjoint J Jᶜ    exact disjoint_compl_right  have hunion : J.edgeFinset ∪ H.edgeFinset = (⊤ : SimpleGraph (Fin 125)).edgeFinset := by    rw [← SimpleGraph.edgeFinset_sup]    change (J ⊔ Jᶜ).edgeFinset = _    exact SimpleGraph.edgeFinset_inj.mpr sup_compl_eq_top  have htotal : J.edgeFinset.card + H.edgeFinset.card = 7750 := by    rw [← Finset.card_union_of_disjoint hdis, hunion, SimpleGraph.card_edgeFinset_top_eq_card_choose_two]    rw [Nat.choose_two_right]    norm_num  have hupper : H.edgeFinset.card ≤ 5168 := by    by_contra hh    exact hnotcolor (hnear H hfree (by omega))  change (42 ≤ 2625 - J.edgeFinset.card ∧ 2625 - J.edgeFinset.card ≤ 43) ∧ ¬ H.Colorable 3  exact ⟨⟨by omega, by omega⟩, hnotcolor⟩
See it in the graphDiscuss this resultChallenge it