AFTD Auto-Formalizing Theoretical Domains

trianglefree_parent_charge_weight_bound

theoremverified

If a charged subset of m parents is proper whenever m is less than four, then three times parents plus charges is bounded by eight times overlap plus one exactly when m is two.

Statement

theorem trianglefree_parent_charge_weight_bound (m c : ℕ)
    (hm : 2 ≤ m) (hc : c ≤ m) (hshort : m < 4 → c < m) :
    3 * (m + c) ≤ 8 * (m - 1) + (if m = 2 then 1 else 0)
Source
Triangle-free center budget for the four-cycle campaign; experiment 13471.
Verified
04 Nov 2026
Axioms
Quot.soundpropext
Used by 1

The proof, explained

The proof proceeds by case analysis on $m \ge 2$. For the small values $m = 2$ and $m = 3$, the hypothesis that $c < m$ whenever $m < 4$ bounds $c$ by $1$ and $2$ respectively, allowing direct computation to verify the inequality. When $m \ge 4$, the conditional bonus term vanishes, and the general bound $c \le m$ yields $3(m + c) \le 6m \le 8(m - 1)$, which holds for all $m \ge 4$.

  1. The inequality holds when $m = 2$.

    We split into cases on whether $m = 2$. Assuming $m = 2$, the hypothesis $m < 4 \to c < m$ gives $c < 2$ (so $c \le 1$), since $2 < 4$ is checked by decision procedure. Substituting $m = 2$, the right-hand side simplifies to $8(2 - 1) + 1 = 9$. Since $c \le 1$, the left-hand side is at most $3(2 + 1) = 9$, which linear arithmetic verifies.

    lines 4–8

      by_cases h2 : m = 2
      · subst m
        have h := hshort (by decide)
        simp
        omega
  2. The inequality holds when $m = 3$.

    Assuming $m \ne 2$, we consider whether $m = 3$. If $m = 3$, the hypothesis $m < 4 \to c < m$ gives $c < 3$ (so $c \le 2$), as $3 < 4$ holds by decision procedure. Because $3 \ne 2$, the conditional indicator evaluates to $0$, simplifying the right-hand side to $8(3 - 1) + 0 = 16$. With $c \le 2$, the left-hand side is at most $3(3 + 2) = 15 \le 16$, which linear arithmetic verifies.

    lines 9–13

      · by_cases h3 : m = 3
        · subst m
          have h := hshort (by decide)
          simp
          omega
  3. The inequality holds for all $m \ge 4$.

    In the remaining case, we have $m \ge 2$, $m \ne 2$, and $m \ne 3$, which implies $m \ge 4$. Simplifying with the hypothesis $m \ne 2$ removes the conditional indicator term, reducing the goal to $3(m + c) \le 8(m - 1)$. Using $c \le m$, the left-hand side is bounded by $6m$; for $m \ge 4$, $6m \le 8m - 8 = 8(m - 1)$, which linear integer arithmetic establishes.

    lines 14–15

        · simp [h2]
          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 trianglefree_parent_charge_weight_bound (m c : ℕ)    (hm : 2 ≤ m) (hc : c ≤ m) (hshort : m < 4 → c < m) :    3 * (m + c) ≤ 8 * (m - 1) + (if m = 2 then 1 else 0) := by  by_cases h2 : m = 2  · subst m    have h := hshort (by decide)    simp    omega  · by_cases h3 : m = 3    · subst m      have h := hshort (by decide)      simp      omega    · simp [h2]      omega
See it in the graphDiscuss this resultChallenge it