odd_div_two_cancel_le
For odd n ≥ 3, if n * (n - 1) / 2 ≤ m * ((n - 1) / 2), then n ≤ m.
Statement
theorem odd_div_two_cancel_le (n m : ℕ) (hn : 3 ≤ n) (hodd : n % 2 = 1) (h : n * (n - 1) / 2 ≤ m * ((n - 1) / 2)) : n ≤ m- Source
- step towards complete_graph_odd_line_graph_le_chromaticNumber
- Verified
- 29 Oct 2026
- Axioms
Quot.soundpropext
The proof, explained
Because n is odd, 2 divides n - 1, which lets us rewrite n * (n - 1) / 2 as n * ((n - 1) / 2). Since n ≥ 3, the factor (n - 1) / 2 is strictly positive, so cancelling it from both sides of the inequality yields n ≤ m.
2 divides n - 1
Since n is odd (n % 2 = 1), n - 1 is even, witnessed explicitly by the quotient n / 2 via linear integer arithmetic (`omega`).
have hdvd : 2 ∣ (n - 1) := ⟨n / 2, by omega⟩
The hypothesis h rewrites to n * ((n - 1) / 2) ≤ m * ((n - 1) / 2)
Because 2 divides n - 1, Nat.mul_div_assoc allows moving the division by 2 inside the product: n * (n - 1) / 2 = n * ((n - 1) / 2).
uses
Nat.mul_div_assocrw [Nat.mul_div_assoc _ hdvd] at h
(n - 1) / 2 > 0
Since n ≥ 3, we have n - 1 ≥ 2, so (n - 1) / 2 ≥ 1 > 0, established by linear integer arithmetic (`omega`).
have hpos : 0 < (n - 1) / 2 := by omega
n ≤ m
Cancelling the strictly positive common factor (n - 1) / 2 from the right of both sides of the inequality h via Nat.le_of_mul_le_mul_right yields n ≤ m.
uses
Nat.le_of_mul_le_mul_rightexact Nat.le_of_mul_le_mul_right h hpos
Nat.mul_div_assoc- For natural numbers m, n, and k, if k divides n, then (m * n) / k = m * (n / k).
Nat.le_of_mul_le_mul_right- For natural numbers a, b, and c, if a * c ≤ b * c and c > 0, then a ≤ b.
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.
/-- For odd n ≥ 3, cancellation of (n - 1) / 2 preserves inequality. -/theorem odd_div_two_cancel_le (n m : ℕ) (hn : 3 ≤ n) (hodd : n % 2 = 1) (h : n * (n - 1) / 2 ≤ m * ((n - 1) / 2)) : n ≤ m := by have hdvd : 2 ∣ (n - 1) := ⟨n / 2, by omega⟩ rw [Nat.mul_div_assoc _ hdvd] at h have hpos : 0 < (n - 1) / 2 := by omega exact Nat.le_of_mul_le_mul_right h hpos