AFTD Auto-Formalizing Theoretical Domains

graph_125_induced_clique_cross_bound

theoremverified

If the 124 vertices outside a distinguished vertex of a graph form three color classes that are cliques, then the number of crossing arcs of any oriented spanning subdigraph among those vertices plus 2501 is at most the graph edge count minus the distinguished vertex degree.

Statement

theorem graph_125_induced_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) :
    let S : Set (Fin 125) := {x}ᶜ
    let H := G.induce S
    let E : Digraph S := ⟨fun u v => D.Adj u.1 v.1⟩
    (∑ u : S, (Finset.univ.filter fun v : S => col v.1 ≠ col u.1 ∧ E.Adj u v).card) + 2501 ≤
      G.edgeFinset.card - G.degree x
Source
Induced-graph crossing bound for the OP-110 exceptional-vertex reduction.
Verified
14 Nov 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 1
Used by 1

The proof, explained

The proof combines an arithmetic optimization lemma with a graph-theoretic clique partition bound. First, a helper lemma (`in833_size124`) establishes that whenever three non-negative integers summing to 124 satisfy $\sum a(a-1) + 2x \le 2e$, the inequality $2501 + x \le e$ follows from the sum-of-squares bound $3(a^2+b^2+c^2) \ge (a+b+c)^2 = 124^2$. Next, deleting the distinguished vertex $x$ leaves an induced subgraph $H$ on the remaining 124 vertices partitioned into three cliques, with edge count $|E(H)| = |E(G)| - \deg_G(x)$. Applying `graph_clique_partition_oriented_cross_degree_bound` gives $\sum n_i(n_i-1) + 2 \cdot \text{cross} \le 2|E(H)|$, which matches the hypothesis of the arithmetic lemma and yields the final bound $\text{cross} + 2501 \le |E(G)| - \deg_G(x)$.

  1. For non-negative integers $a, b, c, x, e$ with $a + b + c = 124$ and $a(a-1) + b(b-1) + c(c-1) + 2x \le 2e$, the sum of squares satisfies $a^2 + b^2 + c^2 + 2x \le 2e + 124$.

    Using the identity $n(n-1) + n = n^2$, verified by case analysis on $n = 0$ and $n = m + 1$, each term $n(n-1)$ is rewritten as $n^2 - n$. Adding the equation $a + b + c = 124$ to the given inequality cancels the linear terms and yields $a^2 + b^2 + c^2 + 2x \le 2e + 124$.

    lines 5–12

      have hprod (n : ℕ) : n*(n-1)+n=n*n := by
        cases n with
        | zero => simp
        | succ n => simp; ring
      have ha := hprod a
      have hb := hprod b
      have hc := hprod c
      have he : a*a+b*b+c*c+2*x ≤ 2*e+124 := by nlinarith
  2. Under the same hypotheses, $2501 + x \le e$ holds.

    Casting the expressions to integers and using the non-negativity of squares $(a-b)^2 \ge 0$, $(a-c)^2 \ge 0$, and $(b-c)^2 \ge 0$ (via `sq_nonneg`), non-linear arithmetic combines $3(a^2 + b^2 + c^2) \ge (a+b+c)^2 = 124^2 = 15376$ with the bound from the previous step to deduce $(2501 : \mathbb{Z}) + x \le e$. Casting back to $\mathbb{N}$ gives $2501 + x \le e$ (`in833_size124`).

    lines 13–19

    uses sq_nonneg

      have hs' : (a:ℤ)+b+c=124 := by exact_mod_cast hs
      have he' : (a:ℤ)*a+b*b+c*c+2*x ≤ 2*e+124 := by exact_mod_cast he
      have h1 : (0:ℤ) ≤ ((a:ℤ)-b)^2 := sq_nonneg _
      have h2 : (0:ℤ) ≤ ((a:ℤ)-c)^2 := sq_nonneg _
      have h3 : (0:ℤ) ≤ ((b:ℤ)-c)^2 := sq_nonneg _
      have out : (2501:ℤ)+x ≤ e := by nlinarith
      exact_mod_cast out
  3. The set $S = \{x\}^c$ of vertices other than $x$ has cardinality 124.

    Working classically, we define $S = \{x\}^c$, the induced subgraph $H = G[S]$, the induced subdigraph $E = D[S]$, the coloring restricted to $S$, the color class sizes $n$, and the crossing arc count `cross`. By `Fintype.card_compl_set`, $|S| = |Fin 125| - |\{x\}| = 125 - 1 = 124$.

    lines 32–42

    uses Fintype.card_compl_set

      classical
      let S : Set (Fin 125) := {x}ᶜ
      let H := G.induce S
      let E : Digraph S := ⟨fun u v => D.Adj u.1 v.1⟩
      let color : S → Fin 3 := fun u => col u.1
      let n : Fin 3 → ℕ := fun i => (Finset.univ.filter fun v : S => color v = i).card
      let cross : ℕ := ∑ u : S, (Finset.univ.filter fun v : S => color v ≠ color u ∧ E.Adj u v).card
      have hcard : Fintype.card S = 124 := by
        dsimp [S]
        rw [Fintype.card_compl_set]
        simp
  4. The sum of the three color class sizes in $S$ is 124: $n(0) + n(1) + n(2) = 124$.

    Partitioning the vertices of $S$ into fibers under the 3-coloring via `Finset.card_eq_sum_card_fiberwise`, the total size $|S| = 124$ equals $\sum_{i \in Fin 3} n(i)$. Expanding this sum over `Fin 3` using `Fin.sum_univ_succ` and `Fin.sum_univ_zero` establishes $n(0) + n(1) + n(2) = 124$.

    lines 43–48

    uses Finset.card_eq_sum_card_fiberwise, Finset.card_univ, Fin.sum_univ_succ, Fin.sum_univ_zero, Nat.add_zero

      have hsizes : n 0+n 1+n 2=124 := by
        have h := Finset.card_eq_sum_card_fiberwise (f := color) (s := (Finset.univ : Finset S))
          (t := (Finset.univ : Finset (Fin 3))) (by simp)
        simp only [Finset.card_univ, hcard, Fin.sum_univ_succ, Fin.sum_univ_zero, Nat.add_zero] at h
        change 124 = n 0+(n 1+n 2) at h
        omega
  5. In the induced subgraph $H$, each color class is a clique, $E$ is a subgraph of $H$, and $E$ is oriented.

    For any two distinct vertices $u, v \in S$ sharing the same color, neither equals $x$ because both lie in $\{x\}^c$ (by `Set.mem_compl_iff` and `Set.mem_singleton_iff`), and their underlying values in `Fin 125` are distinct by `Subtype.ext`. Hence the clique hypothesis `hclique` applies and makes them adjacent in $H$. The subdigraph condition ($E \subseteq H$) and the orientation condition (no mutual arcs in $E$) are directly inherited from $D$ and $G$.

    lines 49–60

    uses Set.mem_compl_iff, Set.mem_singleton_iff, Subtype.ext

      have hc : ∀ u v : S, color u = color v → u ≠ v → H.Adj u v := by
        intro u v hcolor hne
        have hu : u.1 ≠ x := by
          have hp : u.1 ∈ ({x}ᶜ : Set (Fin 125)) := u.2
          simpa only [Set.mem_compl_iff, Set.mem_singleton_iff] using hp
        have hv : v.1 ≠ x := by
          have hp : v.1 ∈ ({x}ᶜ : Set (Fin 125)) := v.2
          simpa only [Set.mem_compl_iff, Set.mem_singleton_iff] using hp
        have huv : u.1 ≠ v.1 := fun h => hne (Subtype.ext h)
        exact hclique u.1 v.1 hu hv hcolor huv
      have hsub' : ∀ u v : S, E.Adj u v → H.Adj u v := fun u v h => hsub u.1 v.1 h
      have hori' : ∀ u v : S, E.Adj u v → ¬ E.Adj v u := fun u v h => hori u.1 v.1 h
  6. The clique partition bound on $H$ expands to $n(0)(n(0)-1) + n(1)(n(1)-1) + n(2)(n(2)-1) + 2 \cdot \text{cross} \le 2 |E(H)|$.

    Applying the general theorem `graph_clique_partition_oriented_cross_degree_bound` to $H$ and $E$ with the 3-coloring yields $\sum_{i \in Fin 3} n(i)(n(i)-1) + 2 \cdot \text{cross} \le 2 |E(H)|$. Unfolding the sum over `Fin 3` via `Fin.sum_univ_succ`, `Fin.sum_univ_zero`, `Fin.succ_zero_eq_one`, `Fin.succ_one_eq_two`, and `Nat.add_zero` rewrites it as the explicit sum of three terms.

    lines 61–68

    uses graph_clique_partition_oriented_cross_degree_bound, Fin.sum_univ_succ, Fin.sum_univ_zero, Fin.succ_zero_eq_one, Fin.succ_one_eq_two, Nat.add_zero

      have hbound := graph_clique_partition_oriented_cross_degree_bound S (Fin 3) H E color hc hsub' hori'
      change (∑ i : Fin 3, n i*(n i-1)) + 2*cross ≤ 2*H.edgeFinset.card at hbound
      have hre : (∑ i : Fin 3, n i*(n i-1)) =
          n 0*(n 0-1)+n 1*(n 1-1)+n 2*(n 2-1) := by
        simp only [Fin.sum_univ_succ, Fin.sum_univ_zero, Fin.succ_zero_eq_one,
          Fin.succ_one_eq_two, Nat.add_zero]
        omega
      rw [hre] at hbound
  7. The crossing arc count plus 2501 is at most $|E(G)| - \deg_G(x)$.

    We apply the arithmetic lemma `in833_size124` with $a = n(0), b = n(1), c = n(2)$, $x = \text{cross}$, and $e = |E(H)|$, using the class sum $n(0) + n(1) + n(2) = 124$ and the clique partition bound, which gives $\text{cross} + 2501 \le |E(H)|$. By `SimpleGraph.card_edgeFinset_induce_compl_singleton` and `SimpleGraph.card_edgeFinset_deleteIncidenceSet`, deleting the vertex $x$ removes exactly its incident edges, so $|E(H)| = |E(G)| - \deg_G(x)$. Substituting this equality concludes the proof.

    lines 69–75

    uses in833_size124, SimpleGraph.card_edgeFinset_induce_compl_singleton, SimpleGraph.card_edgeFinset_deleteIncidenceSet

      have hbase := in833_size124 (n 0) (n 1) (n 2) cross H.edgeFinset.card hsizes hbound
      have hedges : H.edgeFinset.card = G.edgeFinset.card - G.degree x := by
        dsimp [H,S]
        rw [SimpleGraph.card_edgeFinset_induce_compl_singleton, SimpleGraph.card_edgeFinset_deleteIncidenceSet]
      change cross + 2501 ≤ G.edgeFinset.card - G.degree x
      rw [← hedges]
      omega
sq_nonneg
In any linearly ordered semiring, the square of any element is non-negative ($0 \le a^2$).
Fintype.card_compl_set
The cardinality of the complement of a subset $s$ of a finite type equals the cardinality of the whole type minus the cardinality of $s$.
Finset.card_eq_sum_card_fiberwise
The cardinality of a finite set equals the sum of the cardinalities of its fibers under a map whose values lie in a target finite set.
Finset.card_univ
The cardinality of the universal finset `Finset.univ` of a finite type equals `Fintype.card`.
Fin.sum_univ_succ
A sum over `Fin (n + 1)` equals the term at $0$ plus the sum of the remaining terms over `Fin n`.
Fin.sum_univ_zero
A sum over the empty type `Fin 0` is zero.
Nat.add_zero
Adding zero to a natural number leaves it unchanged ($n + 0 = n$).
Set.mem_compl_iff
An element belongs to the complement of a set $s$ if and only if it does not belong to $s$.
Set.mem_singleton_iff
An element $a$ belongs to the singleton $\{b\}$ if and only if $a = b$.
Subtype.ext
Two elements of a subtype are equal if and only if their underlying values are equal.
graph_clique_partition_oriented_cross_degree_bound
If the vertices of a graph $G$ are partitioned into cliques by a coloring and $D$ is an oriented subdigraph of $G$, then the sum of $n_i(n_i-1)$ over all color classes plus twice the number of crossing arcs in $D$ is at most $2|E(G)|$.
Fin.succ_zero_eq_one
The successor of $0$ in `Fin (n + 1)` is $1$.
Fin.succ_one_eq_two
The successor of $1$ in `Fin (n + 1)` is $2$.
in833_size124
For natural numbers $a, b, c, x, e$, if $a + b + c = 124$ and $a(a-1) + b(b-1) + c(c-1) + 2x \le 2e$, then $2501 + x \le e$.
SimpleGraph.card_edgeFinset_induce_compl_singleton
The number of edges in the subgraph induced by removing a single vertex $x$ equals the number of edges after deleting the incidence set of $x$.
SimpleGraph.card_edgeFinset_deleteIncidenceSet
Deleting the edges incident to a vertex $x$ reduces the graph's edge count by the degree of $x$.

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 2500000set_option maxRecDepth 4096private lemma in833_size124 (a b c x e : ℕ) (hs : a+b+c=124)    (hbound : a*(a-1)+b*(b-1)+c*(c-1)+2*x ≤ 2*e) : 2501+x ≤ e := by  have hprod (n : ℕ) : n*(n-1)+n=n*n := by    cases n with    | zero => simp    | succ n => simp; ring  have ha := hprod a  have hb := hprod b  have hc := hprod c  have he : a*a+b*b+c*c+2*x ≤ 2*e+124 := by nlinarith  have hs' : (a:ℤ)+b+c=124 := by exact_mod_cast hs  have he' : (a:ℤ)*a+b*b+c*c+2*x ≤ 2*e+124 := by exact_mod_cast he  have h1 : (0:ℤ) ≤ ((a:ℤ)-b)^2 := sq_nonneg _  have h2 : (0:ℤ) ≤ ((a:ℤ)-c)^2 := sq_nonneg _  have h3 : (0:ℤ) ≤ ((b:ℤ)-c)^2 := sq_nonneg _  have out : (2501:ℤ)+x ≤ e := by nlinarith  exact_mod_cast outtheorem graph_125_induced_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) :    let S : Set (Fin 125) := {x}ᶜ    let H := G.induce S    let E : Digraph S := ⟨fun u v => D.Adj u.1 v.1⟩    (∑ u : S, (Finset.univ.filter fun v : S => col v.1 ≠ col u.1 ∧ E.Adj u v).card) + 2501 ≤      G.edgeFinset.card - G.degree x := by  classical  let S : Set (Fin 125) := {x}ᶜ  let H := G.induce S  let E : Digraph S := ⟨fun u v => D.Adj u.1 v.1⟩  let color : S → Fin 3 := fun u => col u.1  let n : Fin 3 → ℕ := fun i => (Finset.univ.filter fun v : S => color v = i).card  let cross : ℕ := ∑ u : S, (Finset.univ.filter fun v : S => color v ≠ color u ∧ E.Adj u v).card  have hcard : Fintype.card S = 124 := by    dsimp [S]    rw [Fintype.card_compl_set]    simp  have hsizes : n 0+n 1+n 2=124 := by    have h := Finset.card_eq_sum_card_fiberwise (f := color) (s := (Finset.univ : Finset S))      (t := (Finset.univ : Finset (Fin 3))) (by simp)    simp only [Finset.card_univ, hcard, Fin.sum_univ_succ, Fin.sum_univ_zero, Nat.add_zero] at h    change 124 = n 0+(n 1+n 2) at h    omega  have hc : ∀ u v : S, color u = color v → u ≠ v → H.Adj u v := by    intro u v hcolor hne    have hu : u.1 ≠ x := by      have hp : u.1 ∈ ({x}ᶜ : Set (Fin 125)) := u.2      simpa only [Set.mem_compl_iff, Set.mem_singleton_iff] using hp    have hv : v.1 ≠ x := by      have hp : v.1 ∈ ({x}ᶜ : Set (Fin 125)) := v.2      simpa only [Set.mem_compl_iff, Set.mem_singleton_iff] using hp    have huv : u.1 ≠ v.1 := fun h => hne (Subtype.ext h)    exact hclique u.1 v.1 hu hv hcolor huv  have hsub' : ∀ u v : S, E.Adj u v → H.Adj u v := fun u v h => hsub u.1 v.1 h  have hori' : ∀ u v : S, E.Adj u v → ¬ E.Adj v u := fun u v h => hori u.1 v.1 h  have hbound := graph_clique_partition_oriented_cross_degree_bound S (Fin 3) H E color hc hsub' hori'  change (∑ i : Fin 3, n i*(n i-1)) + 2*cross ≤ 2*H.edgeFinset.card at hbound  have hre : (∑ i : Fin 3, n i*(n i-1)) =      n 0*(n 0-1)+n 1*(n 1-1)+n 2*(n 2-1) := by    simp only [Fin.sum_univ_succ, Fin.sum_univ_zero, Fin.succ_zero_eq_one,      Fin.succ_one_eq_two, Nat.add_zero]    omega  rw [hre] at hbound  have hbase := in833_size124 (n 0) (n 1) (n 2) cross H.edgeFinset.card hsizes hbound  have hedges : H.edgeFinset.card = G.edgeFinset.card - G.degree x := by    dsimp [H,S]    rw [SimpleGraph.card_edgeFinset_induce_compl_singleton, SimpleGraph.card_edgeFinset_deleteIncidenceSet]  change cross + 2501 ≤ G.edgeFinset.card - G.degree x  rw [← hedges]  omega
See it in the graphDiscuss this resultChallenge it