$k$-tree.

Note that there is some discrepancy over this definition; certain authors use $K_{k}$ in the base case. This means that $K_{k}$ is a $k$-tree, but creates no other changes. $k$-trees have a strong tie to treewidth; see Lemma \[lemma:ktree\].

A graph is *chordal* if it contains no induced cycle of length at least four. That is, every cycle that is not a triangle contains a chord. @gavril74 showed that the chordal graphs are exactly the intersection graphs of subtrees of a tree $T$. So construct a tree decomposition with underlying tree $T$ as follows. Think of each $v \in V(G)$ as a subtree of $T$; place $v$ in the bags indexed by the nodes of that subtree. It can easily be seen that this is a tree decomposition of $G$ in which every bag is a clique (that is, every possible edge exists), since should two vertices share a bag, then their subtrees intersect and the vertices are adjacent. It also follows that the graph arising from a tree decomposition with all possible edges (that is, two vertices are adjacent if and only if they share a bag) is a chordal graph. Chordal graphs are therefore interesting by being 