AFTD Auto-Formalizing Theoretical Domains

digraph_126_four_cycles_under_extremal_and_cycle_criteria

theoremverified

A loopless oriented seven-outregular digraph on 126 vertices whose arcs have common predecessors and whose every in-neighborhood contains a directed cycle has four disjoint directed cycles, assuming the displayed induced one-, two- and three-cycle criteria and the stated 126-vertex clique-free three-coloring criterion.

Statement

theorem digraph_126_four_cycles_under_extremal_and_cycle_criteria
    (D : Digraph (Fin 126)) [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 126), digraph_directed_cycle_on D C ∧ ∀ w ∈ C, D.Adj w v)
    (hone : ∀ T : Finset (Fin 126), T.Nonempty →
      (∀ v ∈ T, 1 ≤ (T.filter fun w => D.Adj v w).card) →
      ∃ C : Finset (Fin 126), C ⊆ T ∧ digraph_directed_cycle_on D C)
    (htwo : ∀ T : Finset (Fin 126), T.Nonempty →
      (∀ v ∈ T, 3 ≤ (T.filter fun w => D.Adj v w).card) →
      ∃ c : Fin 2 → Finset (Fin 126), (∀ i, c i ⊆ T ∧ digraph_directed_cycle_on D (c i)) ∧
        Pairwise (fun i j => Disjoint (c i) (c j)))
    (hthree : ∀ T : Finset (Fin 126), T.Nonempty →
      (∀ v ∈ T, 5 ≤ (T.filter fun w => D.Adj v w).card) →
      ∃ c : Fin 3 → Finset (Fin 126), (∀ i, c i ⊆ T ∧ digraph_directed_cycle_on D (c i)) ∧
        Pairwise (fun i j => Disjoint (c i) (c j)))
    (hnear : ∀ (G : SimpleGraph (Fin 126)) [DecidableRel G.Adj],
      G.CliqueFree 4 → 5252 ≤ G.edgeFinset.card → G.Colorable 3)
 :
    ∃ c : Fin 4 → Finset (Fin 126), (∀ i, digraph_directed_cycle_on D (c i)) ∧
      Pairwise (fun i j => Disjoint (c i) (c j))
Source
Order-126 exclusion for OP-110, using the three-cycle criterion from https://iti.mff.cuni.cz/series/2007/339.pdf and the near-extremal coloring criterion from https://arxiv.org/abs/1409.8665, Theorem 1.1.
Verified
14 Nov 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 7

The proof, explained

The theorem is proved by contradiction: assume there are no four pairwise disjoint directed cycles in the digraph D. Under this assumption, the common predecessor graph J has no independent set of size 4, so its complement H = Jᶜ is 4-clique-free. A cycle packing theorem implies that J has at most 2604 edges, which forces H to have at least 7875 - 2604 = 5271 ≥ 5252 edges and therefore be 3-colorable by the extremal coloring criterion. This 3-coloring partitions the vertices into three cliques in J, which together with the orientation of D bounds the number of cross-arcs between color classes to at most 21. However, cycle packing criteria on three parts of size at least 7 require at least 45 cross-arcs to avoid four disjoint cycles, producing a contradiction.

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

    For any pair of vertices u and v, adjacency in the common predecessor graph is defined by whether u ≠ v and there exists a common predecessor w in D. Because the vertex type is finite and adjacency in D is decidable, this existential quantification over vertices is decidable.

    lines 5–7

      intro u v
      unfold digraph_common_predecessor_graph
      infer_instance
  2. Assuming there are no four disjoint directed cycles, the complement H = Jᶜ of the common predecessor graph J is 4-clique-free.

    Assume for contradiction that D contains no four pairwise disjoint directed cycles. Let J be the common predecessor graph of D, where distinct vertices are adjacent when they share an in-neighbor, and let H = Jᶜ be its complement graph. Because every in-neighborhood in D contains a directed cycle, the absence of four disjoint cycles implies that J has no independent set of size 4 (digraph_common_predecessor_graph_indep_free_four). An independent set in J is a clique in H, so H is 4-clique-free.

    lines 32–37

    uses digraph_common_predecessor_graph_indep_free_four

      classical
      by_contra hno
      let J := digraph_common_predecessor_graph D
      let H := Jᶜ
      have hindep := digraph_common_predecessor_graph_indep_free_four (Fin 126) D hin hno
      have hfree : H.CliqueFree 4 := by simpa [H,J] using hindep
  3. The sum of the number of pairs of out-neighbors across all vertices is 2646, and each vertex has out-degree at least 5 + 2.

    Because D is 7-outregular, each vertex has (7 choose 2) = 21 unordered pairs of out-neighbors. Summing over all 126 vertices yields 126 * 21 = 2646 pairs. Furthermore, each out-degree 7 is at least 5 + 2.

    lines 38–43

      have hinc : (∑ v : Fin 126, Nat.choose (Finset.univ.filter fun w => D.Adj v w).card 2) = 2646 := 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 graph J has at most 2604 edges.

    If 3 * (2646 - |E(J)|) < 126, the cycle packing step lemma (digraph_small_overlap_cycle_packing_step) combined with the 3-cycle hypothesis (hthree) would produce 3 + 1 = 4 disjoint directed cycles in D, contradicting our assumption. Therefore, 126 ≤ 3 * (2646 - |E(J)|), which implies |E(J)| ≤ 2646 - 42 = 2604.

    lines 44–52

    uses Fintype.card_fin, digraph_small_overlap_cycle_packing_step, SimpleGraph.mem_edgeFinset

      have hz : 126 ≤ 3 * (2646 - J.edgeFinset.card) := by
        by_contra hh
        have hs : 3 * ((∑ v : Fin 126, Nat.choose (Finset.univ.filter fun w => D.Adj v w).card 2) -
          J.edgeFinset.card) < Fintype.card (Fin 126) := by rw [hinc]; simp only [Fintype.card_fin]; omega
        apply hno
        apply digraph_small_overlap_cycle_packing_step (Fin 126) 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 ≤ 2604 := by omega
  5. The sum of the edge counts of J and H is |E(J)| + |E(H)| = 7875.

    The edge sets of J and its complement H = Jᶜ are disjoint (SimpleGraph.disjoint_edgeFinset, disjoint_compl_right), and their union is the edge set of the complete graph on 126 vertices (SimpleGraph.edgeFinset_sup, SimpleGraph.edgeFinset_inj.mpr, sup_compl_eq_top). Thus, the sum of their edge counts is the number of edges in K₁₂₆ (Finset.card_union_of_disjoint), which is (126 choose 2) = 126 * 125 / 2 = 7875 (SimpleGraph.card_edgeFinset_top_eq_card_choose_two, Nat.choose_two_right).

    lines 53–64

    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 126)).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 = 7875 := by
        rw [← Finset.card_union_of_disjoint hdis, hunion, SimpleGraph.card_edgeFinset_top_eq_card_choose_two]
        rw [Nat.choose_two_right]
        norm_num
  6. The complement graph H is 3-colorable, partitioning the vertices into three cliques in J.

    Since |E(J)| ≤ 2604, the complement graph H has |E(H)| = 7875 - |E(J)| ≥ 5271 ≥ 5252 edges. Because H is 4-clique-free, the assumed extremal coloring condition (hnear) implies that H is 3-colorable. Fixing a proper 3-coloring col, no two vertices of the same color can be adjacent in H; by definition of the complement graph (SimpleGraph.compl_adj), any two distinct monochromatic vertices must be adjacent in J. Thus, each color class forms a clique in J.

    lines 65–71

    uses SimpleGraph.compl_adj

      have hcolor : H.Colorable 3 := hnear H hfree (by omega)
      obtain ⟨col⟩ := hcolor
      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
  7. Every directed arc in D is an edge in the common predecessor graph J.

    Let u → v be an arc in D. Because D is loopless (hloop), u ≠ v. By the common predecessor assumption (hdom), u and v share an in-neighbor p. Therefore, u and v are adjacent in J.

    lines 72–79

      have hsubset : ∀ 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⟩
  8. The upper and lower bounds on cross-arcs between the color classes contradict each other, completing the proof.

    Applying the clique partition bound for oriented graphs (graph_126_three_clique_partition_oriented_cross_bound) to J and D, each color class contains at least 7 vertices and the total number of cross-arcs between different color classes in D is at most 21. On the other hand, the three-part cycle packing criterion (digraph_three_large_parts_no_four_cycles_cross_ge_forty_five) implies that in a 7-outregular digraph without four disjoint cycles, three parts of size at least 7 must have at least 45 cross-arcs between them. This forces 45 ≤ 21, an absurdity that refutes the assumption that D has no four disjoint directed cycles.

    lines 80–83

    uses graph_126_three_clique_partition_oriented_cross_bound, digraph_three_large_parts_no_four_cycles_cross_ge_forty_five

      have hb := graph_126_three_clique_partition_oriented_cross_bound J D col hclique hsubset hori hedges
      have hc := digraph_three_large_parts_no_four_cycles_cross_ge_forty_five (Fin 126) D col
        hb.1 (by intro v; rw [hreg v]) hone htwo hthree hno
      omega
Fintype.card_fin
The cardinality of the 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 Gᶜ if and only if they are distinct and not adjacent in G.
SimpleGraph.disjoint_edgeFinset
Two simple graphs have disjoint edge finite sets if and only if they are disjoint as graphs.
SimpleGraph.edgeFinset_sup
The finite edge set of the union (join) of two simple graphs is the union of their respective finite edge sets.
SimpleGraph.edgeFinset_inj.mpr
If two simple graphs on the same vertex type are equal, then their finite edge sets are equal.
SimpleGraph.card_edgeFinset_top_eq_card_choose_two
The number of edges in the complete simple graph on a finite vertex set V is (card V) choose 2.
SimpleGraph.mem_edgeFinset
An unordered pair belongs to the finite edge set of a simple graph if and only if it is an edge in its edge set.
digraph_common_predecessor_graph_indep_free_four
If every in-neighborhood in a digraph contains a directed cycle, and the digraph contains no four pairwise disjoint directed cycles, then its common predecessor graph has no independent set of size 4.
digraph_small_overlap_cycle_packing_step
In a loopless digraph with minimum out-degree at least d + 2 where every arc has a common predecessor, if 3 times the difference between the total pairs of out-arcs and the number of edges of the common predecessor graph is less than the number of vertices, and any induced subdigraph with minimum out-degree at least d contains k disjoint directed cycles, then the whole digraph contains k + 1 disjoint directed cycles.
digraph_three_large_parts_no_four_cycles_cross_ge_forty_five
If a 7-outregular digraph partitioned into three parts of size at least 7 contains no four disjoint directed cycles and satisfies the 1-, 2-, and 3-cycle criteria, then it has at least 45 cross-arcs between the three parts.
disjoint_compl_right
Any element is disjoint from its complement in a Heyting algebra or Boolean algebra.
graph_126_three_clique_partition_oriented_cross_bound
If a simple graph on 126 vertices with at most 2604 edges is partitioned into three cliques and contains the arcs of an oriented digraph, then each clique has at least 7 vertices and the digraph has at most 21 cross-arcs between the cliques.
sup_compl_eq_top
The join of any element with its complement in a Boolean algebra 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_decidable {α : 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_126_four_cycles_under_extremal_and_cycle_criteria    (D : Digraph (Fin 126)) [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 126), digraph_directed_cycle_on D C ∧ ∀ w ∈ C, D.Adj w v)    (hone : ∀ T : Finset (Fin 126), T.Nonempty →      (∀ v ∈ T, 1 ≤ (T.filter fun w => D.Adj v w).card) →      ∃ C : Finset (Fin 126), C ⊆ T ∧ digraph_directed_cycle_on D C)    (htwo : ∀ T : Finset (Fin 126), T.Nonempty →      (∀ v ∈ T, 3 ≤ (T.filter fun w => D.Adj v w).card) →      ∃ c : Fin 2 → Finset (Fin 126), (∀ i, c i ⊆ T ∧ digraph_directed_cycle_on D (c i)) ∧        Pairwise (fun i j => Disjoint (c i) (c j)))    (hthree : ∀ T : Finset (Fin 126), T.Nonempty →      (∀ v ∈ T, 5 ≤ (T.filter fun w => D.Adj v w).card) →      ∃ c : Fin 3 → Finset (Fin 126), (∀ i, c i ⊆ T ∧ digraph_directed_cycle_on D (c i)) ∧        Pairwise (fun i j => Disjoint (c i) (c j)))    (hnear : ∀ (G : SimpleGraph (Fin 126)) [DecidableRel G.Adj],      G.CliqueFree 4 → 5252 ≤ G.edgeFinset.card → G.Colorable 3) :    ∃ c : Fin 4 → Finset (Fin 126), (∀ 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  let H := Jᶜ  have hindep := digraph_common_predecessor_graph_indep_free_four (Fin 126) D hin hno  have hfree : H.CliqueFree 4 := by simpa [H,J] using hindep  have hinc : (∑ v : Fin 126, Nat.choose (Finset.univ.filter fun w => D.Adj v w).card 2) = 2646 := 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 : 126 ≤ 3 * (2646 - J.edgeFinset.card) := by    by_contra hh    have hs : 3 * ((∑ v : Fin 126, Nat.choose (Finset.univ.filter fun w => D.Adj v w).card 2) -      J.edgeFinset.card) < Fintype.card (Fin 126) := by rw [hinc]; simp only [Fintype.card_fin]; omega    apply hno    apply digraph_small_overlap_cycle_packing_step (Fin 126) 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 ≤ 2604 := by 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 126)).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 = 7875 := 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 hcolor : H.Colorable 3 := hnear H hfree (by omega)  obtain ⟨col⟩ := hcolor  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 hsubset : ∀ 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 hb := graph_126_three_clique_partition_oriented_cross_bound J D col hclique hsubset hori hedges  have hc := digraph_three_large_parts_no_four_cycles_cross_ge_forty_five (Fin 126) D col    hb.1 (by intro v; rw [hreg v]) hone htwo hthree hno  omega
See it in the graphDiscuss this resultChallenge it