Proof sketch of Lemma 2.2, pp. 321–322 — components with ≤ ½|S| of S each can be split into two sides with ≤ ⅔|S| of S each
ProvedTreewidthApprox.Pushed.packing_argumentThis is the packing step in the proof sketch of Lemma 2.2.
Let be a finite graph and . Suppose every connected component of satisfies . Then the components of can be distributed between a left side and a right side so that each side holds at most two thirds of : there are disjoint sets with , no edge of between and , and
Combined with Lemma 2.1 this gives, for every graph of treewidth at most , a set of at most vertices whose removal splits into two sides of at most each; with it is the folklore -balanced separation used in Lemma 6.5.
Formalization Note "Assigning each component to the left or the right" is encoded as a partition of with no edge between and : such a partition is exactly a union of components on each side. No treewidth hypothesis is needed and none is assumed. The bounds are stated without division as and .
import Mathlib import Definitions.Def_TreewidthApprox_Pushed_Setting
namespace TreewidthApprox.Pushed
theorem packing_argument {V : Type} [Fintype V] [DecidableEq V] (G : SimpleGraph V)
(S X' : Finset V)
(hX' : ∀ u : V, u ∉ X' → 2 * (avoidComp G X' u ∩ S).card ≤ S.card) :
∃ Lft Rgt : Finset V, Disjoint Lft Rgt ∧ Lft ∪ Rgt = Finset.univ \ X' ∧
NoEdge G Lft Rgt ∧
3 * (Lft ∩ S).card ≤ 2 * S.card ∧ 3 * (Rgt ∩ S).card ≤ 2 * S.card := by sorry
end TreewidthApprox.Pushed
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.