Lemma 2.9 — balanced S-separators and three non-adjacent parts
ProvedTreewidthApprox.Partition.lemma_2_9Let be a finite simple graph, , and . The set is a balanced -separator exactly when has a partition into three sets such that distinct parts have no edges between them and each part contains at most half the vertices of :
The equivalence replaces a condition on every connected component by conditions on three vertex sets.
Formalization Note Parts may be empty; in particular, is included. The three unordered pairs suffice because adjacency is symmetric. Cardinality bounds use natural numbers with denominators cleared, and retains its full cardinality even when it meets . The component relation uses walks avoiding at every vertex. No bound on or treewidth is assumed. Lean uses a vertex type in universe 0, consistently with this series.
import Mathlib import Definitions.Def_TreewidthApprox_Partition_Setting
namespace TreewidthApprox.Partition
/-- Lemma 2.9, p. 328 (restated as Lemma 6.2, p. 363). -/
theorem lemma_2_9 {V : Type} [Fintype V] [DecidableEq V]
(G : SimpleGraph V) (S X : Finset V) :
IsBalancedSSep G S X ↔
∃ M₁ M₂ M₃ : Finset V,
Disjoint M₁ M₂ ∧ Disjoint M₁ M₃ ∧ Disjoint M₂ M₃ ∧
M₁ ∪ M₂ ∪ M₃ = Finset.univ \ X ∧
TreewidthApprox.Pushed.NoEdge G M₁ M₂ ∧ TreewidthApprox.Pushed.NoEdge G M₁ M₃ ∧ TreewidthApprox.Pushed.NoEdge G M₂ M₃ ∧
2 * (M₁ ∩ S).card ≤ S.card ∧
2 * (M₂ ∩ S).card ≤ S.card ∧
2 * (M₃ ∩ S).card ≤ S.card := by sorry
end TreewidthApprox.Partition
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.