Normalize a partial-decomposition leaf to its flap and boundary
ProvedMazoit2013.leaf_normalizationIn a finite graph, let a partial tree decomposition have bag threshold b and a large leaf t attached to u. Write X for its flap, the vertices in the leaf bag but not the attachment bag. Replacing that leaf bag by X together with its external graph boundary preserves the partial decomposition at threshold b. It creates no new flaps and preserves every flap other than X. If the replacement bag is small, X disappears. The boundary and replacement are explicitly constructed; no gluing or separator-minimality hypothesis is assumed.
Preamble
import Definitions.Def_Mazoit2013_PartialDecompositions open RobertsonSeymour1986.GM5 StableMSR.Recovery.Havens StableMSR.Recovery.PartialDecompositions
Formal statement
theorem Mazoit2013.leaf_normalization {V T : Type} [Fintype V] [DecidableEq V] [DecidableEq T]
{G : SimpleGraph V} {b : ℕ} {tree : SimpleGraph T} {bags : T → Finset V}
(h : IsPartial G b tree bags) {t u : T} (hbig : b < (bags t).card)
(htu : tree.Adj t u) :
∃ B : Finset V,
(∀ y, y ∈ B ↔ y ∈ bags t \ bags u ∨
(y ∉ bags t \ bags u ∧ ∃ x ∈ bags t \ bags u, G.Adj x y)) ∧
B ⊆ bags t ∧
IsPartial G b tree (Function.update bags t B) ∧
flaps b tree (Function.update bags t B) ⊆ flaps b tree bags ∧
(∀ C ∈ flaps b tree bags, C ≠ bags t \ bags u →
C ∈ flaps b tree (Function.update bags t B)) ∧
(B.card ≤ b → bags t \ bags u ∉ flaps b tree (Function.update bags t B)) := by sorrySource
Mazoit, A simple proof of the tree-width duality theorem, https://arxiv.org/pdf/1309.2266, p. 2, partial decompositions and the preparation for Lemma 1. Explicit normalization lemma for this formalization.