digraph_125_four_cycles_under_extremal_and_cycle_criteria
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
- 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…
- graph_125_noncolorable_complement_high_degreeIf a 125-vertex graph has independence number at most three and its complement is not three-colorable, then it has a vertex of degree at…
- graph_125_high_degree_delete_complement_coloringIf a graph on 125 vertices has independence number at most three and at most 2583 edges, deleting a vertex of degree at least 46 leaves a…
- finset_three_color_busiest_recolorGiven three colors and a finite set excluding a distinguished point, recolor only that point so that at least one third of the set has its…
- graph_125_three_cliques_except_vertex_boundsIf a graph on 125 vertices has at most 2583 edges and its vertices other than one distinguished vertex form three cliques, then at least…
- graph_125_exceptional_three_clique_cross_boundFor an oriented subdigraph of a graph on 125 vertices, suppose the vertices other than a distinguished vertex form three color classes…
- digraph_125_no_four_cycles_overlap_windowFor a loopless oriented seven-outregular digraph on 125 vertices with dominated arcs, a cycle in each in-neighborhood, and no four…
- digraph_common_predecessor_vertex_incidence_boundFor an r-outregular finite digraph, the number of common-predecessor edge incidences repeated at a given vertex is at most the total…
- digraph_three_large_parts_no_four_cycles_cross_ge_fifty_fourIf a finite digraph of minimum outdegree seven has no four disjoint directed cycles and its vertices are partitioned into three parts each…
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.
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.
intro u v unfold digraph_common_predecessor_graph infer_instance
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.
uses
digraph_common_predecessor_graph_indep_free_four,digraph_125_no_four_cycles_overlap_windowclassical 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
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.
uses
graph_125_noncolorable_complement_high_degree,graph_125_high_degree_delete_complement_coloringobtain ⟨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
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.
uses
finset_three_color_busiest_recolorlet 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
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.
uses
graph_125_three_cliques_except_vertex_boundshave ⟨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
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.
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⟩
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.
uses
digraph_common_predecessor_vertex_incidence_boundhave 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
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.
uses
Finset.disjoint_left.mpr,Finset.card_union_of_disjointhave 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
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.
uses
graph_125_exceptional_three_clique_cross_boundhave hcross := graph_125_exceptional_three_clique_cross_bound J D x col hclique hsub hori (hreg x) hmax hdegree hwin.1 hbound hcap hbThe 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.
uses
le_trans,Finset.card_le_card,digraph_three_large_parts_no_four_cycles_cross_ge_fifty_fourhave 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.
- The private instance at lines 3–7 establishes decidability of adjacency in the common predecessor graph, which is required by Lean's typeclass synthesis for edge counting, complement operations, and coloring predicates.
- The proof makes extensive use of the omega tactic to close linear integer arithmetic goals resulting from edge, degree, and neighborhood bounds.
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 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