# A clique in a tree decomposition is contained in a bag

Let $$G$$ be a graph, $$T$$ a tree and $$\mathcal{V}=\bigcup_{t \in T} V_t$$ a tree decomposition of $$G$$. Let $$H \subseteq G$$ be a clique. Show that $$H$$ is contained in a bag $$V_t$$ for some vertex $$t \in T$$.

I've tried an induction on the size of the clique without success. I assume the proof relies on the fact that trees contain no cycles (i.e. given any two vertices $$a,b \in T$$, there is a unqiue path $$a \rightarrow b$$.

Any help would be grateful.

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.

The following is a non-induction proof, where we construct such a bag containing $$H$$ and verify it by the properties of trees.

Proof. Root $$T$$ arbitrarily. For each $$v\in H$$, define $$L_v :=\{t\in T|v\in V_t\}$$, i.e., $$L_v$$ is the set of all labels of bags containing $$v$$. Then we choose the label of minimal depth(distance from the root) in $$L_v$$, denoted by $$l_v$$. Let $$l_{m}$$ be the label of maximum depth in $$\{l_v|v\in H\}$$ and $$m\in H$$. Then we claim that the bag $$V_{l_{m}}$$ contains $$H$$.

To prove our claim, we first observe that for any $$v\in H\setminus \{m\}$$, $$L_v$$ induces a subtree $$T[L_v]$$ rooted in $$l_v$$ and edge $$(v,m)\in E(G)$$. Then by the definition of tree decomposition, tree $$T[L_v]$$ and tree $$T[L_m]$$ have at least one node in common, i.e., $$L_m \cap L_v \ne \emptyset$$ (as illustrated in the figure above, the two trees share two nodes). For any node $$l_x \in L_m\cap L_v$$, there is a unique path from $$l_x$$ to $$l_v$$. This path must go through $$l_m$$. Again by the definition of tree decomposition, we have $$V_{l_m} \supseteq V_{l_x}\cap V_{l_v}$$. Thus, $$v\in V_{l_m}$$. $$\square$$