AFTD Auto-Formalizing Theoretical Domains

girth_parent_charge_weight_bound

theoremverified

A charged subset of m parents satisfying the girth-dependent proper-subset condition has the displayed weighted parent-plus-charge bound.

Statement

theorem girth_parent_charge_weight_bound (g m c : ℕ)
    (hg : 3 ≤ g) (hm : 2 ≤ m) (hc : c ≤ m)
    (hshort : m < g → c < m) :
    (g - 1) * (m + c) ≤ 2 * g * (m - 1) + (g + 1 - 2 * m)
Source
Girth-dependent center budget for the four-cycle campaign; experiment 13474.
Verified
04 Nov 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 2
  • TotalPreorderA total preorder: a preorder where ≤ is total (complete). This is weaker than LinearOrder — it does NOT require antisymmetry or…
  • LinearOrder.toTotalPreorderEvery LinearOrder is a TotalPreorder.
Used by 1

The proof, explained

The proof establishes the inequality $(g - 1)(m + c) \le 2g(m - 1) + (g + 1 - 2m)$ by splitting into two cases: $m < g$ and $m \ge g$. Before the split, it derives three distributive identities that express the products $(g - 1)m$, $(g - 1)(m - 1)$, and $g(m - 1)$ in terms of $gm$. When $m < g$, the condition implies $c \le m - 1$, matching the bound with the correction term $g + 1 - 2m$; when $m \ge g$, the inequalities $c \le m$ and $g \le m$ allow $(g - 1)(m + c) \le 2(g - 1)m$ to be bounded directly by $2g(m - 1)$.

  1. $(g - 1) + 1 = g$ and $(m - 1) + 1 = m$.

    Since $g \ge 3$ and $m \ge 2$, both $g$ and $m$ are positive (at least 1). Subtracting 1 and then adding 1 returns the original number by linear arithmetic over $\mathbb{N}$.

    lines 5–6

      have hg1 : (g - 1) + 1 = g := by omega
      have hm1 : (m - 1) + 1 = m := by omega
  2. $(g - 1)m + m = gm$, $(g - 1)(m - 1) + (m - 1) = g(m - 1)$, and $g(m - 1) + g = gm$.

    These identities rewrite products involving the decremented values $g - 1$ and $m - 1$ in terms of $gm$. Factoring $m$ out of $(g - 1)m + m$ via right-distributivity (Nat.add_mul) gives $((g - 1) + 1)m = gm$. Similarly, factoring $m - 1$ out of $(g - 1)(m - 1) + (m - 1)$ gives $((g - 1) + 1)(m - 1) = g(m - 1)$ (Nat.add_mul). Finally, factoring $g$ out of $g(m - 1) + g$ via left-distributivity (Nat.mul_add) gives $g((m - 1) + 1) = gm$.

    lines 7–18

    uses Nat.add_mul, Nat.mul_add

      have hp1 : (g - 1) * m + m = g * m := by
        calc
          (g - 1) * m + m = ((g - 1) + 1) * m := by simp [Nat.add_mul]
          _ = g * m := by rw [hg1]
      have hp2 : (g - 1) * (m - 1) + (m - 1) = g * (m - 1) := by
        calc
          (g - 1) * (m - 1) + (m - 1) = ((g - 1) + 1) * (m - 1) := by simp [Nat.add_mul]
          _ = g * (m - 1) := by rw [hg1]
      have hp3 : g * (m - 1) + g = g * m := by
        calc
          g * (m - 1) + g = g * ((m - 1) + 1) := by simp [Nat.mul_add]
          _ = g * m := by rw [hm1]
  3. The bound $(g - 1)(m + c) \le 2g(m - 1) + (g + 1 - 2m)$ holds when $m < g$.

    Assuming $m < g$, the short-path hypothesis (hshort) yields $c < m$, hence $c \le m - 1$. Multiplying by $g - 1$ yields $(g - 1)c \le (g - 1)(m - 1)$ by Nat.mul_le_mul_left. In addition, the truncated natural subtraction inequality $g + 1 \le 2m + (g + 1 - 2m)$ holds. Combining $(g - 1)(m + c) = (g - 1)m + (g - 1)c \le (g - 1)m + (g - 1)(m - 1)$ with the three product identities and this inequality, nonlinear arithmetic establishes the claim.

    lines 19–23

    uses Nat.mul_le_mul_left

      by_cases hmg : m < g
      · have hc' : c ≤ m - 1 := by have := hshort hmg; omega
        have hscale := Nat.mul_le_mul_left (g - 1) hc'
        have hcorr : g + 1 ≤ 2 * m + (g + 1 - 2 * m) := by omega
        nlinarith [hp1,hp2,hp3]
  4. The bound $(g - 1)(m + c) \le 2g(m - 1) + (g + 1 - 2m)$ holds when $m \ge g$.

    Assuming $m \ge g$ (that is, $g \le m$), we scale the assumption $c \le m$ by $g - 1$ to get $(g - 1)c \le (g - 1)m$ via Nat.mul_le_mul_left. Then $(g - 1)(m + c) \le 2(g - 1)m = 2(gm - m)$. Because $g \le m$, we have $2(gm - m) \le 2(gm - g) = 2g(m - 1)$. Since the final truncated term $g + 1 - 2m \ge 0$, the desired inequality follows by nonlinear arithmetic using the product identities.

    lines 24–26

    uses Nat.mul_le_mul_left

      · have hge : g ≤ m := by omega
        have hscale := Nat.mul_le_mul_left (g - 1) hc
        nlinarith [hp1,hp3]
Nat.add_mul
Multiplication distributes over addition on the right: $(n + m) \cdot k = n \cdot k + m \cdot k$.
Nat.mul_add
Multiplication distributes over addition on the left: $n \cdot (m + k) = n \cdot m + n \cdot k$.
Nat.mul_le_mul_left
Multiplying an inequality on the left by a natural number preserves the inequality: if $n \le m$, then $k \cdot n \le k \cdot m$.

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 girth_parent_charge_weight_bound (g m c : ℕ)    (hg : 3 ≤ g) (hm : 2 ≤ m) (hc : c ≤ m)    (hshort : m < g → c < m) :    (g - 1) * (m + c) ≤ 2 * g * (m - 1) + (g + 1 - 2 * m) := by  have hg1 : (g - 1) + 1 = g := by omega  have hm1 : (m - 1) + 1 = m := by omega  have hp1 : (g - 1) * m + m = g * m := by    calc      (g - 1) * m + m = ((g - 1) + 1) * m := by simp [Nat.add_mul]      _ = g * m := by rw [hg1]  have hp2 : (g - 1) * (m - 1) + (m - 1) = g * (m - 1) := by    calc      (g - 1) * (m - 1) + (m - 1) = ((g - 1) + 1) * (m - 1) := by simp [Nat.add_mul]      _ = g * (m - 1) := by rw [hg1]  have hp3 : g * (m - 1) + g = g * m := by    calc      g * (m - 1) + g = g * ((m - 1) + 1) := by simp [Nat.mul_add]      _ = g * m := by rw [hm1]  by_cases hmg : m < g  · have hc' : c ≤ m - 1 := by have := hshort hmg; omega    have hscale := Nat.mul_le_mul_left (g - 1) hc'    have hcorr : g + 1 ≤ 2 * m + (g + 1 - 2 * m) := by omega    nlinarith [hp1,hp2,hp3]  · have hge : g ≤ m := by omega    have hscale := Nat.mul_le_mul_left (g - 1) hc    nlinarith [hp1,hp3]
See it in the graphDiscuss this resultChallenge it