girth_parent_charge_weight_bound
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 thanLinearOrder— it does NOT require antisymmetry or… - LinearOrder.toTotalPreorderEvery
LinearOrderis aTotalPreorder.
- TotalPreorderA total preorder: a preorder where
- Used by 1
- digraph_girth_arc_map_weighted_budgetFor a loopless oriented digraph of directed girth at least g, with g at least three and chosen common predecessors for its arcs, g−1 times…
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)$.
$(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}$.
have hg1 : (g - 1) + 1 = g := by omega have hm1 : (m - 1) + 1 = m := by omega
$(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$.
uses
Nat.add_mul,Nat.mul_addhave 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]
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.
uses
Nat.mul_le_mul_leftby_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]
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.
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$.
- In natural number arithmetic, subtraction truncates at zero ($a - b = 0$ when $a \le b$). Thus expressions such as $g + 1 - 2m$ denote truncated subtraction, and inequalities like $g + 1 \le 2m + (g + 1 - 2m)$ hold unconditionally in $\mathbb{N}$.
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 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]