graph_125_exceptional_three_clique_cross_bound
For an oriented subdigraph of a graph on 125 vertices, suppose the vertices other than a distinguished vertex form three color classes that are cliques, the graph has the displayed edge and degree bounds, and the distinguished vertex has seven outgoing arcs and is assigned a color containing at least one third of its incident arcs. Under the displayed overlap and indegree inequalities, at most 50 arcs cross the colors.
Statement
theorem graph_125_exceptional_three_clique_cross_bound (G : SimpleGraph (Fin 125)) [DecidableRel G.Adj] (D : Digraph (Fin 125)) [DecidableRel D.Adj] (x : Fin 125) (col : Fin 125 → Fin 3) (hclique : ∀ u v, u ≠ x → v ≠ x → col u = col v → u ≠ v → G.Adj u v) (hsub : ∀ u v, D.Adj u v → G.Adj u v) (hori : ∀ u v, D.Adj u v → ¬ D.Adj v u) (hout : (Finset.univ.filter fun w => D.Adj x w).card = 7) (hedges : G.edgeFinset.card ≤ 2625) (hdeg : 46 ≤ G.degree x) (hoverlap : 42 ≤ 2625 - G.edgeFinset.card ∧ 2625 - G.edgeFinset.card ≤ 43) (hbound : 6 * (Finset.univ.filter fun w => D.Adj w x).card ≤ G.degree x + (2625 - G.edgeFinset.card)) (hcap : G.degree x + (2625 - G.edgeFinset.card) ≤ 124) (hbalanced : (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) : (∑ v : Fin 125, (Finset.univ.filter fun w => col w ≠ col v ∧ D.Adj v w).card) ≤ 50
- Source
- Exceptional-vertex counting reduction for OP-110; experiment 26134 checks its numerical budget.
- Verified
- 14 Nov 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 4
- graph_clique_partition_oriented_cross_degree_boundIf the color classes of a finite graph are cliques and an oriented digraph is a spanning subgraph, then twice its number of crossing arcs…
- graph_125_exceptional_coloring_arithmeticThe displayed overlap, degree, indegree and color-class budget inequalities imply a total crossing budget of at most fifty.
- graph_125_induced_clique_cross_boundIf the 124 vertices outside a distinguished vertex of a graph form three color classes that are cliques, then the number of crossing arcs…
- digraph_three_color_cross_arcs_delete_vertex_splitThe number of arcs crossing three vertex colors equals the number crossing among the vertices other than a distinguished vertex plus the…
- Used by 1
- digraph_125_four_cycles_under_extremal_and_cycle_criteriaA loopless oriented seven-outregular digraph on 125 vertices with dominated arcs and a cycle in every in-neighborhood contains four…
The proof, explained
The proof bounds the total number of cross-color arcs in D by decomposing them into the cross-color arcs within the 124-vertex subgraph induced by deleting x and the cross-color arcs incident to x. An established clique bound limits the cross-color arcs on the remaining vertices to at most 124 - z - d, while the incident cross-color arcs are counted as 7 + t - |A| using the orientation and neighborhood partition of x. An arithmetic lemma then combines these bounds with the degree, edge deficiency, and color-balance hypotheses to conclude that the total is at most 50.
Define the induced subdigraph on the remaining 124 vertices, the neighborhood subsets of x, and relevant arithmetic parameters.
We let S = {x}ᶜ be the set of 124 vertices other than x, E be the subdigraph of D induced on S, and rest be the number of cross-color arcs in E. We define O and I as the sets of out-neighbors and in-neighbors of x in D, and M = O ∪ I as its full neighborhood in D. Within M, we define A as the neighbors sharing the color of x, OC as the cross-color out-neighbors, and IC as the cross-color in-neighbors. Finally, we set t = |I| (the in-degree of x), d = deg_G(x), and z = 2625 - |E(G)| (the edge deficiency).
classical let S : Set (Fin 125) := {x}ᶜ let E : Digraph S := ⟨fun u v => D.Adj u.1 v.1⟩ let rest : ℕ := ∑ u : S, (Finset.univ.filter fun v : S => col v.1 ≠ col u.1 ∧ E.Adj u v).card 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 let A := M.filter fun w => col w = col x let OC := O.filter fun w => col w ≠ col x let IC := I.filter fun w => col w ≠ col x let t := I.card let z := 2625 - G.edgeFinset.card let d := G.degree x
The in-neighborhood and out-neighborhood of x are disjoint, and therefore their cross-color subsets are also disjoint.
Since D is an oriented graph, there are no mutual arcs between x and any vertex, meaning no vertex can belong to both O and I. Because OC ⊆ O and IC ⊆ I, the disjointness of O and I implies that OC and IC are disjoint as well.
uses
Finset.disjoint_left.mpr,Finset.mem_filter.mp,Finset.disjoint_left.mphave 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 hdC : Disjoint OC IC := by apply Finset.disjoint_left.mpr intro v hv1 hv2 exact Finset.disjoint_left.mp hdOI (Finset.mem_filter.mp hv1).1 (Finset.mem_filter.mp hv2).1
The total neighborhood M has cardinality 7 + t.
Because O and I are disjoint, the cardinality of M = O ∪ I is |O| + |I|. Since |O| = 7 by hypothesis and |I| = t by definition, this gives |M| = 7 + t.
uses
Finset.card_union_of_disjointhave hM : M.card = 7+t := by rw [Finset.card_union_of_disjoint hdOI] change O.card = 7 at hout omega
The neighborhood M partitions into monochromatic neighbors and cross-color neighbors, giving |A| + |OC| + |IC| = 7 + t.
The neighbors of x having the same color as x form exactly A, while those with a different color decompose into OC ∪ IC. Partitioning M by whether a neighbor shares the color of x, and using the disjointness of OC and IC, shows that |M| = |A| + |OC| + |IC|. Equating this to |M| = 7 + t gives the identity.
uses
Finset.mem_filter,Finset.mem_union,Finset.mem_univ,true_and,Finset.card_filter_add_card_filter_not,Finset.card_union_of_disjointhave hsame : (Finset.univ.filter fun w => col w = col x ∧ (D.Adj x w ∨ D.Adj w x)) = A := by ext w simp only [A,M,O,I, Finset.mem_filter, Finset.mem_union, Finset.mem_univ, true_and] tauto have hcross : M.filter (fun w => col w ≠ col x) = OC ∪ IC := by ext w simp only [OC,IC,M,O,I, Finset.mem_filter, Finset.mem_union, Finset.mem_univ, true_and] tauto have hparts : A.card + OC.card + IC.card = 7+t := by have hp := Finset.card_filter_add_card_filter_not (s := M) (fun w => col w = col x) change A.card + (M.filter fun w => col w ≠ col x).card = M.card at hp rw [hcross, Finset.card_union_of_disjoint hdC,hM] at hp omega
The color-balance condition simplifies to t + 7 ≤ 3|A|.
Rewriting the balance hypothesis using the identification of monochromatic neighbors of x with the set A directly yields t + 7 ≤ 3|A|.
have hb : t+7 ≤ 3*A.card := by rw [hsame] at hbalanced exact hbalanced
The number of cross-color arcs within S is at most 124 - z - d.
Applying the clique bound lemma graph_125_induced_clique_cross_bound to the induced subgraph on S gives rest + 2501 ≤ |E(G)| - d. Substituting |E(G)| = 2625 - z yields rest ≤ (2625 - z) - d - 2501 = 124 - z - d.
uses
graph_125_induced_clique_cross_boundhave hr : rest + 2501 ≤ G.edgeFinset.card - d := by have h := graph_125_induced_clique_cross_bound G D x col hclique hsub hori exact h have hrest : rest ≤ 124-z-d := by omega
The numerical bound (124 - z - d) + (t + 7 - |A|) ≤ 50 holds.
Applying the arithmetic lemma graph_125_exceptional_coloring_arithmetic to the parameters z, d, t, and |A| with the hypotheses 42 ≤ z ≤ 43, 46 ≤ d, 6t ≤ d + z, d + z ≤ 124, and t + 7 ≤ 3|A| establishes the inequality.
uses
graph_125_exceptional_coloring_arithmetichave hnum := graph_125_exceptional_coloring_arithmetic z d t A.card hoverlap.1 hoverlap.2 hdeg hbound hcap hbThe total number of cross-color arcs in D equals rest + |OC| + |IC|.
By digraph_three_color_cross_arcs_delete_vertex_split, deleting vertex x partitions all cross-color arcs into those contained entirely in S (which is rest), those directed out of x to a different color (which equals OC), and those directed into x from a different color (which equals IC).
uses
digraph_three_color_cross_arcs_delete_vertex_split,and_commhave hs := digraph_three_color_cross_arcs_delete_vertex_split (Fin 125) D x col have hsplit : (∑ v : Fin 125, (Finset.univ.filter fun w => col w ≠ col v ∧ D.Adj v w).card) = rest + OC.card + IC.card := by have ho : (Finset.univ.filter fun w => col w ≠ col x ∧ D.Adj x w) = OC := by ext w simp [OC,O, and_comm] have hi : (Finset.univ.filter fun w => col w ≠ col x ∧ D.Adj w x) = IC := by ext w simp [IC,I, and_comm] rw [ho,hi] at hs exact hs
At most 50 arcs in D cross the colors.
Substituting the decomposition, the total number of cross-color arcs is rest + |OC| + |IC|. Since |OC| + |IC| = 7 + t - |A| and rest ≤ 124 - z - d, the sum is bounded by (124 - z - d) + (t + 7 - |A|), which is at most 50 by the arithmetic bound.
rw [hsplit] omega
Finset.disjoint_left.mpr- Two finite sets are disjoint if no element of the first belongs to the second.
Finset.disjoint_left.mp- If two finite sets are disjoint, no element of the first belongs to the second.
Finset.mem_filter.mp- An element in a filtered finite set satisfies the filtering predicate and belongs to the original set.
Finset.card_union_of_disjoint- The cardinality of the union of two disjoint finite sets is the sum of their cardinalities.
Finset.mem_filter- An element belongs to a filtered finite set if and only if it belongs to the base set and satisfies the predicate.
Finset.mem_union- An element belongs to the union of two finite sets if and only if it belongs to at least one of them.
Finset.mem_univ- Every element of a finite type belongs to its universal finset.
true_and- Conjunction of True with any proposition is equivalent to the proposition.
Finset.card_filter_add_card_filter_not- For any predicate on a finite set, the number of elements satisfying it plus the number not satisfying it equals the total cardinality.
graph_125_induced_clique_cross_bound- In a 125-vertex graph where all vertices other than x form three clique color classes, the number of cross-color arcs in the oriented subdigraph on the remaining vertices plus 2501 is at most the total edge count minus the degree of x.
graph_125_exceptional_coloring_arithmetic- A system of linear integer inequalities ensuring that under the given bounds on edge deficiency z, vertex degree d, in-degree t, and monochromatic neighbors a, the quantity (124 - z - d) + (t + 7 - a) is at most 50.
digraph_three_color_cross_arcs_delete_vertex_split- The total number of cross-color arcs in a 3-colored digraph decomposes into the cross-color arcs within the subgraph obtained by deleting a vertex x, plus the cross-color arcs leaving x, plus the cross-color arcs entering x.
and_comm- Conjunction is commutative: a ∧ b is equivalent to b ∧ a.
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 3000000set_option maxRecDepth 4096theorem graph_125_exceptional_three_clique_cross_bound (G : SimpleGraph (Fin 125)) [DecidableRel G.Adj] (D : Digraph (Fin 125)) [DecidableRel D.Adj] (x : Fin 125) (col : Fin 125 → Fin 3) (hclique : ∀ u v, u ≠ x → v ≠ x → col u = col v → u ≠ v → G.Adj u v) (hsub : ∀ u v, D.Adj u v → G.Adj u v) (hori : ∀ u v, D.Adj u v → ¬ D.Adj v u) (hout : (Finset.univ.filter fun w => D.Adj x w).card = 7) (hedges : G.edgeFinset.card ≤ 2625) (hdeg : 46 ≤ G.degree x) (hoverlap : 42 ≤ 2625 - G.edgeFinset.card ∧ 2625 - G.edgeFinset.card ≤ 43) (hbound : 6 * (Finset.univ.filter fun w => D.Adj w x).card ≤ G.degree x + (2625 - G.edgeFinset.card)) (hcap : G.degree x + (2625 - G.edgeFinset.card) ≤ 124) (hbalanced : (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) : (∑ v : Fin 125, (Finset.univ.filter fun w => col w ≠ col v ∧ D.Adj v w).card) ≤ 50 := by classical let S : Set (Fin 125) := {x}ᶜ let E : Digraph S := ⟨fun u v => D.Adj u.1 v.1⟩ let rest : ℕ := ∑ u : S, (Finset.univ.filter fun v : S => col v.1 ≠ col u.1 ∧ E.Adj u v).card 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 let A := M.filter fun w => col w = col x let OC := O.filter fun w => col w ≠ col x let IC := I.filter fun w => col w ≠ col x let t := I.card let z := 2625 - G.edgeFinset.card let d := G.degree x 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 hdC : Disjoint OC IC := by apply Finset.disjoint_left.mpr intro v hv1 hv2 exact Finset.disjoint_left.mp hdOI (Finset.mem_filter.mp hv1).1 (Finset.mem_filter.mp hv2).1 have hM : M.card = 7+t := by rw [Finset.card_union_of_disjoint hdOI] change O.card = 7 at hout omega have hsame : (Finset.univ.filter fun w => col w = col x ∧ (D.Adj x w ∨ D.Adj w x)) = A := by ext w simp only [A,M,O,I, Finset.mem_filter, Finset.mem_union, Finset.mem_univ, true_and] tauto have hcross : M.filter (fun w => col w ≠ col x) = OC ∪ IC := by ext w simp only [OC,IC,M,O,I, Finset.mem_filter, Finset.mem_union, Finset.mem_univ, true_and] tauto have hparts : A.card + OC.card + IC.card = 7+t := by have hp := Finset.card_filter_add_card_filter_not (s := M) (fun w => col w = col x) change A.card + (M.filter fun w => col w ≠ col x).card = M.card at hp rw [hcross, Finset.card_union_of_disjoint hdC,hM] at hp omega have hb : t+7 ≤ 3*A.card := by rw [hsame] at hbalanced exact hbalanced have hr : rest + 2501 ≤ G.edgeFinset.card - d := by have h := graph_125_induced_clique_cross_bound G D x col hclique hsub hori exact h have hrest : rest ≤ 124-z-d := by omega have hnum := graph_125_exceptional_coloring_arithmetic z d t A.card hoverlap.1 hoverlap.2 hdeg hbound hcap hb have hs := digraph_three_color_cross_arcs_delete_vertex_split (Fin 125) D x col have hsplit : (∑ v : Fin 125, (Finset.univ.filter fun w => col w ≠ col v ∧ D.Adj v w).card) = rest + OC.card + IC.card := by have ho : (Finset.univ.filter fun w => col w ≠ col x ∧ D.Adj x w) = OC := by ext w simp [OC,O, and_comm] have hi : (Finset.univ.filter fun w => col w ≠ col x ∧ D.Adj w x) = IC := by ext w simp [IC,I, and_comm] rw [ho,hi] at hs exact hs rw [hsplit] omega