triangle_reduction_clique_counting_obstruction
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
LinearOrderis aTotalPreorder. - TotalPreorderA total preorder: a preorder where
≤is total (complete). This is weaker thanLinearOrder— it does NOT require antisymmetry or…
- LinearOrder.toTotalPreorderEvery
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².
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².
have hx : x ≤ 3 * k * m + 3 * k * k := by nlinarith
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².
have hsum : k * m ≤ 2 * h + 2 * k * k := by nlinarith
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.
uses
Nat.mul_pos,Nat.sub_add_cancel,congrArg,Nat.mul_addhave 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
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).
have hq19 : 19 * k ≤ q := by omega
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.
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
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.
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.
- Because arithmetic is performed over the natural numbers ℕ, truncated subtraction must be handled explicitly: identities like (q - 1) + 1 = q and the expansion of k * m around 2q + 2k are verified manually so that nlinarith can reason about them without underflow.
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 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