Every clique lies in a bag of a finite tree decomposition
ProvedStableMSR.Recovery.clique_in_decomposition_bagclusteringgraph-theorytreewidth
Let be a graph and let be a tree decomposition with a finite, nonempty decomposition tree. Every finite clique of is contained in one bag:
The empty clique is included. The graph itself need not be finite.
This is the bag-placement fact used to assign the clustering algorithm's clique-supported constraints and contributions to individual bags. The proof establishes the Helly property of nonempty path-convex vertex sets in a finite tree, then applies it to the bag occurrences of the clique vertices. It uses the canonical path-based definition of tree decomposition.
Preamble
import Definitions.Def_RobertsonSeymour1986_GM5_IsTreeDecomposition set_option autoImplicit false open scoped Classical
Formal statement
namespace StableMSR.Recovery
theorem clique_in_decomposition_bag {V T : Type} [DecidableEq V] [Fintype T] [DecidableEq T]
(G : SimpleGraph V) (tree : SimpleGraph T) (bags : T → Finset V)
(htd : RobertsonSeymour1986.GM5.IsTreeDecomposition G tree bags)
(K : Finset V) (hK : (K : Set V).Pairwise G.Adj) :
∃ t : T, K ⊆ bags t := by sorry
end StableMSR.Recovery
Source
Ravichandran and Reyzin, Exact Sum-of-Radii Clustering under Any Constant Stability, https://arxiv.org/html/2611.03547v1, Appendix A.6, tree-decomposition paragraph: every clique lies in a bag, so constraints and contributions can be assigned to containing bags. The finite-tree Helly argument is formalized directly.