AFTD Auto-Formalizing Theoretical Domains

triangle_reduction_clique_counting_obstruction

theoremverified

The displayed natural-number inequalities for the four types of packed triangles, cover size, and uncovered cross edges are inconsistent when k is positive and the outside set has size at least 40k.

Statement

theorem triangle_reduction_clique_counting_obstruction
    (k m a b c d x h q : ℕ)
    (hk : 0 < k) (hm : 40 * k ≤ m)
    (hcross : 2 * (a + b) ≤ k * m)
    (hinside : 2 * (b + c) ≤ k * k)
    (hbudget : x ≤ 2 * (a + b + c + d))
    (hpacked : 3 * d ≤ x)
    (hcover : k * m + a + 3 * d ≤ x + h)
    (hmax : h ≤ k * q)
    (hclique : q * (q - 1) ≤ 2 * x) : False
Source
Counting step toward simple_graph_complete_no_small_vertex_triangle_reduction in the triangle packing-cover campaign.
Verified
04 Nov 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 2
  • LinearOrder.toTotalPreorderEvery LinearOrder is a TotalPreorder.
  • TotalPreorderA total preorder: a preorder where ≤ is total (complete). This is weaker than LinearOrder — it does NOT require antisymmetry or…

The proof, explained

The proof derives a chain of bounds that forces an order-of-magnitude contradiction between the linear budget on x and the quadratic clique lower bound. From the packing, budget, and edge inequalities, one obtains x ≤ 3km + 3k² and km ≤ 2h + 2k², which together with h ≤ kq forces m ≤ 2q + 2k. Since m ≥ 40k, this implies q ≥ 19k; but then q(q - 1) grows quadratically in q and cannot be bounded by 2x, which is at most 12kq + 18k².

  1. x ≤ 3 * k * m + 3 * k * k automation

    Nonlinear arithmetic combines the packing bound 3d ≤ x with the budget inequality x ≤ 2(a + b + c + d) to eliminate d, giving x ≤ 6(a + b + c). Then the bounds on cross edges 2(a + b) ≤ km and inside edges 2(b + c) ≤ k² yield x ≤ 3km + 3k².

    line 11

      have hx : x ≤ 3 * k * m + 3 * k * k := by nlinarith
  2. k * m ≤ 2 * h + 2 * k * k automation

    Nonlinear arithmetic combines the cover inequality km + a + 3d ≤ x + h with the budget and edge bounds, canceling the contribution of d and bounding the remaining terms by 2h + 2k².

    line 12

      have hsum : k * m ≤ 2 * h + 2 * k * k := by nlinarith
  3. m ≤ 2 * q + 2 * k

    Suppose for contradiction that m > 2q + 2k. Then m - (2q + 2k) is strictly positive, so its product with k is strictly positive by Nat.mul_pos. Applying Nat.sub_add_cancel with congrArg and Nat.mul_add decomposes km into k * (m - (2q + 2k)) + k * (2q + 2k). Since the first term is at least k > 0, we have km > 2kq + 2k², which contradicts km ≤ 2h + 2k² because h ≤ kq.

    lines 13–23

    uses Nat.mul_pos, Nat.sub_add_cancel, congrArg, Nat.mul_add

      have hq : m ≤ 2 * q + 2 * k := by
        by_contra hn
        have hp : 0 < k * (m - (2 * q + 2 * k)) := by
          apply Nat.mul_pos hk
          omega
        have heq : k * m = k * (m - (2 * q + 2 * k)) + k * (2 * q + 2 * k) := by
          have hle : 2 * q + 2 * k ≤ m := by omega
          have hc := congrArg (fun t : ℕ => k * t) (Nat.sub_add_cancel hle)
          rw [Nat.mul_add] at hc
          exact hc.symm
        nlinarith
  4. 19 * k ≤ q automation

    Linear integer arithmetic deduces 19k ≤ q from the lower bound m ≥ 40k and the upper bound m ≤ 2q + 2k (which together imply 40k ≤ 2q + 2k, hence 38k ≤ 2q).

    line 24

      have hq19 : 19 * k ≤ q := by omega
  5. q ≤ k * q, 19 * k * k ≤ k * q, 1 ≤ q, and (q - 1) + 1 = q automation

    Since k > 0, multiplying by k shows q ≤ kq and 19k² ≤ kq. Because k ≥ 1 and q ≥ 19k, we have q ≥ 19 ≥ 1, which ensures that truncated subtraction on ℕ satisfies (q - 1) + 1 = q.

    lines 25–28

      have hkq : q ≤ k * q := by nlinarith
      have hkq2 : 19 * k * k ≤ k * q := by nlinarith
      have hqpos : 1 ≤ q := by omega
      have hqsub : q - 1 + 1 = q := by omega
  6. False automation

    The clique inequality q(q - 1) ≤ 2x combined with x ≤ 3km + 3k² and m ≤ 2q + 2k implies q² - q ≤ 12kq + 18k². However, since q ≥ 19k, the quadratic term q² grows as at least 19kq, which exceeds 12kq + 18k² (using 19k² ≤ kq and q ≥ 1), yielding a contradiction via nonlinear arithmetic.

    line 29

      nlinarith
Nat.mul_pos
The product of two strictly positive natural numbers is strictly positive.
congrArg
Applying a function to both sides of an equality preserves the equality.
Nat.sub_add_cancel
For natural numbers with m ≤ n, subtracting m and then adding m yields n ((n - m) + m = n).
Nat.mul_add
Left distributivity of multiplication over addition: n * (m + k) = n * m + n * k.

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 triangle_reduction_clique_counting_obstruction    (k m a b c d x h q : ℕ)    (hk : 0 < k) (hm : 40 * k ≤ m)    (hcross : 2 * (a + b) ≤ k * m)    (hinside : 2 * (b + c) ≤ k * k)    (hbudget : x ≤ 2 * (a + b + c + d))    (hpacked : 3 * d ≤ x)    (hcover : k * m + a + 3 * d ≤ x + h)    (hmax : h ≤ k * q)    (hclique : q * (q - 1) ≤ 2 * x) : False := by  have hx : x ≤ 3 * k * m + 3 * k * k := by nlinarith  have hsum : k * m ≤ 2 * h + 2 * k * k := by nlinarith  have hq : m ≤ 2 * q + 2 * k := by    by_contra hn    have hp : 0 < k * (m - (2 * q + 2 * k)) := by      apply Nat.mul_pos hk      omega    have heq : k * m = k * (m - (2 * q + 2 * k)) + k * (2 * q + 2 * k) := by      have hle : 2 * q + 2 * k ≤ m := by omega      have hc := congrArg (fun t : ℕ => k * t) (Nat.sub_add_cancel hle)      rw [Nat.mul_add] at hc      exact hc.symm    nlinarith  have hq19 : 19 * k ≤ q := by omega  have hkq : q ≤ k * q := by nlinarith  have hkq2 : 19 * k * k ≤ k * q := by nlinarith  have hqpos : 1 ≤ q := by omega  have hqsub : q - 1 + 1 = q := by omega  nlinarith
See it in the graphDiscuss this resultChallenge it