A clique in a tree decomposition is contained in a bag

Proof by induction. This is true for cliques of size 2 by the definition of tree decomposition.

Suppose this is true for cliques of size k and you are given a clique S of size k+1. Choose some $v\in S$ and let $S_0=S-\{v\}$. By the hypothesis, there is some $t\in T$ such that $S_0 \subseteq V_t$ - denote by $T_0$ the set of all such $t$'s (which is actually a subtree). If one of them also contains $v$, then we are done, so assume (by negation) that $v$ can be found only in $V_t$ such that $t\notin T_0$.

The set $T-T_0$ is a forest. If $t_1,t_2\in T-T_0$ are in different connected components and $v \in V_{t_1}\cap V_{t_2}$, then $v$ must be in all the vertices on the path connecting them. This path must go through $T_0$ contradicting our assumption. It follows that there is some connected component $C$ of $T-T_0$ such that $v$ can appear only there. Since $T$ is a tree, there is a unique edge between $T_0$ and $C$ which we denote by $(t_0,c_0)\in T\times C$.

For each $u\in S_0$ there is some $t\in T$ such that $\{u,v\} \in V_t$ by the definition of tree decomposition (this is an edge in the clique $S$), and thus they all must be in $C$. The path from each of these vertices to $t_0$ must go through $c_0$, and because $u\in V_{t_0}$ we get that $u\in V_{c_0}$ for every $u\in S_0$ which means that $c_0\in T_0$ - contradiction.

Tags:

Graph Theory