Cardinality sum of a finite disjoint cover
ProvedWilliamsonShmoys_partition_card_sum__p2m_fd88c45a_7ea7_48a7_9749_c5d6b2241812_a5approximation-algorithmsplanar-graphstreewidth
For a finite family of pairwise disjoint finite sets covering V, the sum of their cardinalities equals the cardinality of V.
Preamble
import Mathlib set_option autoImplicit false
Formal statement
theorem WilliamsonShmoys_partition_card_sum__p2m_fd88c45a_7ea7_48a7_9749_c5d6b2241812_a5 {V : Type} [Fintype V] (parts : Finset (Finset V)) (hcover : ∀ v, ∃ s ∈ parts, v ∈ s) (hdisj : ∀ s ∈ parts, ∀ t ∈ parts, s ≠ t → Disjoint s t) : ∑ s ∈ parts, s.card = Fintype.card V := by sorrySource
David P. Williamson and David B. Shmoys, The Design of Approximation Algorithms, Cambridge University Press, 2011, author electronic manuscript, Section 10.2, proof of Theorem 10.11, pp. 270-272. https://doi.org/10.1017/CBO9780511921735. Bounded tree-width of the pieces: Robertson–Seymour (planar graphs of radius r have tree-width at most 3r+1) / Bodlaender (k-outerplanar graphs have tree-width at most 3k-1).