trianglefree_parent_charge_weight_bound
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
- digraph_trianglefree_arc_map_weighted_budgetFor a loopless oriented digraph of directed girth at least four with chosen common predecessors for its arcs, three times the number of…
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$.
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.
by_cases h2 : m = 2 · subst m have h := hshort (by decide) simp omega
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.
· by_cases h3 : m = 3 · subst m have h := hshort (by decide) simp omega
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.
· 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
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 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