AFTD Auto-Formalizing Theoretical Domains

graph_125_exceptional_three_clique_cross_bound

theoremverified

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
Used by 1

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.

  1. 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).

    lines 20–32

      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
  2. 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.

    lines 33–40

    uses Finset.disjoint_left.mpr, Finset.mem_filter.mp, Finset.disjoint_left.mp

      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
  3. 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.

    lines 41–44

    uses Finset.card_union_of_disjoint

      have hM : M.card = 7+t := by
        rw [Finset.card_union_of_disjoint hdOI]
        change O.card = 7 at hout
        omega
  4. 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.

    lines 45–57

    uses Finset.mem_filter, Finset.mem_union, Finset.mem_univ, true_and, Finset.card_filter_add_card_filter_not, Finset.card_union_of_disjoint

      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
  5. 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|.

    lines 58–60

      have hb : t+7 ≤ 3*A.card := by
        rw [hsame] at hbalanced
        exact hbalanced
  6. 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.

    lines 61–64

    uses graph_125_induced_clique_cross_bound

      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
  7. 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.

    line 65

    uses graph_125_exceptional_coloring_arithmetic

      have hnum := graph_125_exceptional_coloring_arithmetic z d t A.card hoverlap.1 hoverlap.2 hdeg hbound hcap hb
  8. The 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).

    lines 66–76

    uses digraph_three_color_cross_arcs_delete_vertex_split, and_comm

      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
  9. 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.

    lines 77–78

      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

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
See it in the graphDiscuss this resultChallenge it