We will drop the superscripts when the graph G is clear from context. Recall that the complete graph on r nodes is called an r clique and is denoted by K r . 1 are k trees. We turn to another main result of this section. The following four conditions are equivalent.
G is a k tree.
G is connected, G has a k clique, but not a k 2 clique, and every minimal x y separator of G is a k clique. On simple characterization of k-trees , Disc. To prove this for k trees on more than k vertices, we need only show that in every such k tree, every maximal clique is a maximum clique, since a maximal clique in a k tree corresponds to a maximal independent set in its complement. Hence, the size of a maximal clique for a k tree is bounded by k 1. D. J. Rose.