For any fixed constant
k, the partial
k-trees are closed under the operation of
graph minors, and therefore, by the
Robertson–Seymour theorem, this family can be characterized in terms of a finite set of
forbidden minors. The partial 1-trees are exactly the
forests, and their single forbidden minor is a triangle. For the partial 2-trees the single forbidden minor is the
complete graph on four vertices. However, the number of forbidden minors increases for larger values of
k. For partial 3-trees there are four forbidden minors: the complete graph on five vertices, the
octahedral graph with six vertices, the eight-vertex
Wagner graph, and the
pentagonal prism with ten vertices. ==Dynamic programming==