6
$\begingroup$

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.

$\endgroup$

2 Answers 2

6
$\begingroup$

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.

$\endgroup$
0
$\begingroup$

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$.

two trees

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$

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .