digraph_126_four_cycles_under_extremal_and_cycle_criteria
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
- 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_common_predecessor_graphThe simple graph joining distinct vertices that have a common in-neighbor in the digraph.
- digraph_common_predecessor_graph_indep_free_fourIf each in-neighborhood of a finite digraph contains a directed cycle and the digraph has no four disjoint directed cycles, then its…
- digraph_small_overlap_cycle_packing_stepThe k-cycle theorem at outdegree d implies the (k+1)-cycle theorem for loopless arc-dominated digraphs of minimum outdegree at least d+2…
- digraph_three_large_parts_no_four_cycles_cross_ge_forty_fiveIf a finite digraph of minimum outdegree seven has no four disjoint directed cycles and its vertices are partitioned into three parts each…
- graph_126_three_clique_partition_oriented_cross_boundFor a graph on 126 vertices partitioned into three cliques, with at most 2604 graph edges, each part has at least seven vertices and every…
- OrderAn order of dimension d is a permutation of the attribute set {0, ..., d-1}, represented as a list without duplicates containing all…
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.
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.
intro u v unfold digraph_common_predecessor_graph infer_instance
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.
uses
digraph_common_predecessor_graph_indep_free_fourclassical 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
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.
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]
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.
uses
Fintype.card_fin,digraph_small_overlap_cycle_packing_step,SimpleGraph.mem_edgeFinsethave 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
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).
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_righthave 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
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.
uses
SimpleGraph.compl_adjhave 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
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.
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⟩
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.
uses
graph_126_three_clique_partition_oriented_cross_bound,digraph_three_large_parts_no_four_cycles_cross_ge_forty_fivehave 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).
- Lines 5–7 establish an auxiliary decidability instance for adjacency in the common predecessor graph, which Lean requires for finite set operations on 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
Choose a tactic — a marked line — to see the goals Lean had before and after it, as in Lean’s infoview. Step with ← → or j k.
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