graph_125_exceptional_coloring_arithmetic
The displayed overlap, degree, indegree and color-class budget inequalities imply a total crossing budget of at most fifty.
Statement
theorem graph_125_exceptional_coloring_arithmetic (z d t a : ℕ)
(hzlo : 42 ≤ z) (hzhi : z ≤ 43) (hd : 46 ≤ d)
(ht : 6 * t ≤ d + z) (hcap : d + z ≤ 124)
(ha : t + 7 ≤ 3 * a) :
(124 - z - d) + (t + 7 - a) ≤ 50- Source
- Exceptional-vertex arithmetic for OP-110; experiment 26134.
- Verified
- 14 Nov 2026
- Axioms
Quot.soundpropext- 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 theorem establishes an upper bound of 50 on the linear expression (124 - z - d) + (t + 7 - a) subject to linear inequality constraints on the natural variables z, d, t, and a. Because both the hypotheses and the conclusion fall within Presburger arithmetic, the result is discharged directly by the `omega` decision procedure.
(124 - z - d) + (t + 7 - a) ≤ 50 automation
The bound follows by linear arithmetic over the natural numbers: the lower bounds z ≥ 42 and d ≥ 46 ensure d + z ≥ 88, which leaves at most 124 - 88 = 36 for the first term; the constraint 6t ≤ d + z then restricts t ≤ 14, which together with t + 7 ≤ 3a bounds the second term t + 7 - a by at most 14, yielding an overall sum of at most 50. The Presburger arithmetic decision procedure `omega` verifies this automatically.
omega
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.
theorem graph_125_exceptional_coloring_arithmetic (z d t a : ℕ) (hzlo : 42 ≤ z) (hzhi : z ≤ 43) (hd : 46 ≤ d) (ht : 6 * t ≤ d + z) (hcap : d + z ≤ 124) (ha : t + 7 ≤ 3 * a) : (124 - z - d) + (t + 7 - a) ≤ 50 := by omega