Proof of `Lifting a tree decomposition through a bounded blow-up`
groundedproofs/Lax263307Proofs/BlowUpDecompositions.lean · lax-263307
What this proof establishes
Assuming the claims on the left, the claim on the right holds — checked by the archive's pipeline. Proof code is not displayed here.
Description
The lifted tree decomposition has bags bounded by the original bag size times the largest fibre size.
Proof strategy
Construct the lifted decomposition on the original tree. A copy occurs at exactly the nodes where its original vertex occurs, preserving connected bag indices. Count each lifted bag with the lift-cardinality statement and bound all fibre sizes by .
Attribution
Bonnet–Chang, proof of Lemma 16.