Treewidth of Cliques
In any tree decomposition of a graph containing a clique there is a node i in T such that contains all the nodes of the clique. This is shown by induction on the size of the clique. The base cases are cliques of size 1 and 2, which follow from the conditions 1 and 2 on a tree decomposition. The inductive case is a graph containing a clique of size k+1, where k is 2 or greater. Let C be the set of nodes in the clique. Since, there are at least three nodes in the clique, call them x, y and z. We know from the induction hypothesis that there are nodes a, b and c in the tree decomposition with
- , .
In a tree there is exactly one path between any two nodes. A second property of trees is that the three paths between a, b and c have a non-empty intersection. Let v be a node in this intersection. From condition 3 on a tree decomposition we get that
This implies that .
It follows from this that the treewidth of a k-clique is k-1.
Read more about this topic: Tree Decomposition
Famous quotes containing the word cliques:
“Unless the people can choose their leaders and rulers, and can revoke their choice at intervals long enough to test their measures by results, the government will be a tyranny exercised in the interests of whatever classes or castes or mobs or cliques have this choice.”
—George Bernard Shaw (1856–1950)