AFTD Auto-Formalizing Theoretical Domains

graph_125_exceptional_coloring_arithmetic

theoremverified

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

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.

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

    line 6

      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

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