graph_125_induced_clique_cross_bound
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
- 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…
- Used by 1
- 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…
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)$.
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$.
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
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`).
uses
sq_nonneghave 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
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$.
uses
Fintype.card_compl_setclassical 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
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$.
uses
Finset.card_eq_sum_card_fiberwise,Finset.card_univ,Fin.sum_univ_succ,Fin.sum_univ_zero,Nat.add_zerohave 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
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$.
uses
Set.mem_compl_iff,Set.mem_singleton_iff,Subtype.exthave 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
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.
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_zerohave 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
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.
uses
in833_size124,SimpleGraph.card_edgeFinset_induce_compl_singleton,SimpleGraph.card_edgeFinset_deleteIncidenceSethave 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$.
- The proof relies on an integer-cast helper lemma (`in833_size124`) to deduce $2501 + x \le e$ from the sum-of-squares inequality $(a-b)^2 + (a-c)^2 + (b-c)^2 \ge 0$, which is verified by the `nlinarith` decision procedure over $\mathbb{Z}$.
- Subtype coercions between the vertex subset $S = \{x\}^c$ and the full type `Fin 125` are handled via `Subtype.ext` and set complement membership simplification.
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 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