Proof of Lemma 4.3, p. 350 — summing the bounds for the children's subtrees: |V(T)| ≤ 1 − p + (1 + 1/(1−C)) Σ μ(vᵢ)
ProvedTreewidthApprox.TreeMeasure.summed_boundLet be a finite rooted tree with root , let and satisfy the hypotheses (i)–(iii) of Lemma 4.3, and write
Let be a vertex with children (), and let and be the subtrees rooted at and at its children. If every child satisfies , then
This is the inequality obtained in the induction step of the proof of Lemma 4.3 by summing the induction hypotheses for the subtrees rooted at the children; its content is that is together with the disjoint union of the .
Formalization Note is the subtree size of the referenced rooted-tree definition; is the number of children of . The paper states the step at the root of the whole tree; stating it at an arbitrary vertex of a fixed tree is the same statement for the subtree . Hypotheses (i)–(iii) are carried for uniformity although this step does not use them.
import Mathlib import Definitions.Def_HarelTarjan_Compressed_RootedTree import Definitions.Def_TreewidthApprox_TreeMeasure_Setting
namespace TreewidthApprox.TreeMeasure
open HarelTarjan.Compressed
theorem summed_bound {V : Type*} [Fintype V] [DecidableEq V] (T : RootedTree V)
(μ : V → ℝ) (C : ℝ) (hC₀ : 0 < C) (hC₁ : C < 1)
(h₁ : ∀ v, 1 ≤ μ v)
(h₂ : ∀ v, ∑ c ∈ children T v, μ c ≤ μ v)
(h₃ : ∀ v c, IsChild T v c → μ c ≤ C * μ v)
(v : V)
(hIH : ∀ c ∈ children T v, (size T c : ℝ) ≤ (1 + 1 / (1 - C)) * μ c - 1) :
(size T v : ℝ) ≤
1 - ((children T v).card : ℝ) + (1 + 1 / (1 - C)) * ∑ c ∈ children T v, μ c := by sorry
end TreewidthApprox.TreeMeasure
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.